{"id":125836,"date":"2020-05-03T13:53:30","date_gmt":"2020-05-03T05:53:30","guid":{"rendered":"http:\/\/4563.org\/?p=125836"},"modified":"2020-05-03T13:53:30","modified_gmt":"2020-05-03T05:53:30","slug":"leetcode-lintcode-%e9%a2%98%e8%a7%a3-%e7%be%8e%e5%9b%a2%e9%9d%a2%e8%af%95%e9%a2%98%ef%bc%9a%e6%9c%80%e7%bb%88%e4%bc%98%e6%83%a0%e4%bb%b7","status":"publish","type":"post","link":"http:\/\/4563.org\/?p=125836","title":{"rendered":"[leetcode\/lintcode \u9898\u89e3] \u7f8e\u56e2\u9762\u8bd5\u9898\uff1a\u6700\u7ec8\u4f18\u60e0\u4ef7"},"content":{"rendered":"
\n
\n
\n

[leetcode\/lintcode \u9898\u89e3] \u7f8e\u56e2\u9762\u8bd5\u9898\uff1a\u6700\u7ec8\u4f18\u60e0\u4ef7 <\/h1>\n

<\/p>\n

\n
\u8cc7\u6df1\u5927\u4f6c : hakunamatata11 <\/span> <\/i> 9<\/span> <\/div>\n
<\/div>\n<\/p><\/div>\n<\/p><\/div>\n<\/p><\/div>\n
<\/p>\n

[\u9898\u76ee\u63cf\u8ff0]<\/h2>\n

\u4e00\u4f4d\u5e97\u4e3b\u9700\u8981\u5b8c\u6210\u4e00\u9879\u9500\u552e\u4efb\u52a1\uff0c\u4ed6\u5c06\u8981\u51fa\u552e\u7684\u7269\u54c1\u6392\u6210\u4e00\u6392\u3002 \u4ece\u5de6\u4fa7\u5f00\u59cb\uff0c\u5e97\u4e3b\u4ee5\u5176\u5168\u4ef7\u51cf\u53bb\u4f4d\u4e8e\u8be5\u7269\u54c1\u53f3\u4fa7\u7684\u7b2c\u4e00\u4e2a\u4ef7\u683c\u8f83\u4f4e\u6216\u4ef7\u683c\u76f8\u540c\u7684\u5546\u54c1\u7684\u4ef7\u683c\u3002<\/p>\n

\u5982\u679c\u53f3\u4fa7\u6ca1\u6709\u4ef7\u683c\u4f4e\u4e8e\u6216\u7b49\u4e8e\u5f53\u524d\u5546\u54c1\u4ef7\u683c\u7684\u5546\u54c1\uff0c\u5219\u4ee5\u5168\u4ef7\u51fa\u552e\u5f53\u524d\u5546\u54c1\u3002<\/p>\n

\u4f60\u9700\u8981\u8fd4\u56de\u6bcf\u4e00\u4e2a\u7269\u54c1\u5b9e\u9645\u552e\u51fa\u4ef7\u683c\u3002<\/p>\n

\u5728\u7ebf\u8bc4\u6d4b\u5730\u5740: https:\/\/www.lintcode.com\/problem\/final-discounted-price\/?utm_source=sc-v2ex-fks<\/p>\n

\u793a\u4f8b 1:<\/p>\n

\u8f93\u5165: Prices = [2, 3, 1, 2, 4, 2] \u8f93\u51fa: [1, 2, 1, 0, 2, 2] \u89e3\u91ca\uff1a\u7b2c 0 \u4e2a\u548c\u7b2c 1 \u4e2a\u7269\u54c1\u53f3\u8fb9\u7b2c\u4e00\u4e2a\u66f4\u4f4e\u7684\u4ef7\u683c\u90fd\u662f 1\uff0c\u6240\u4ee5\u5b9e\u9645\u552e\u4ef7\u9700\u8981\u5728\u5168\u4ef7\u4e0a\u51cf\u53bb 1\uff0c \u7b2c 3 \u4e2a\u7269\u54c1\u53f3\u8fb9\u7b2c\u4e00\u4e2a\u66f4\u4f4e\u7684\u4ef7\u683c\u662f 2\uff0c\u6240\u4ee5\u5b9e\u9645\u552e\u4ef7\u8981\u5728\u5168\u4ef7\u4e0a\u9762\u51cf\u53bb 2 \u3002 <\/code><\/pre>\n
\u793a\u4f8b 2:<\/p>\n
\u8f93\u5165: Prices = [1, 2, 3, 4, 5] \u8f93\u51fa: [1, 2, 3, 4, 5] \u89e3\u91ca: \u6bcf\u4e00\u4e2a\u7269\u54c1\u90fd\u4fdd\u6301\u539f\u4ef7\uff0c\u4ed6\u4eec\u7684\u53f3\u8fb9\u90fd\u6ca1\u6709\u7b49\u4e8e\u6216\u8005\u66f4\u4f4e\u4ef7\u683c\u7684\u7269\u54c1 <\/code><\/pre>\n
[\u9898\u89e3]<\/h2>\n
public class Solution {     \/**      * @param prices: a list of integer      * @return: return the actual prices      *\/     public int[] FinalDiscountedPrice(int[] prices) {         \/\/ write your code here         int[] res = new int[prices.length];         Stack<Integer> s = new Stack<>();          for(int i = 0;i < prices.length;i++) res[i] = prices[i];          for(int i = 0;i < prices.length;i++){             while(!s.isEmpty() && prices[s.peek()] >= prices[i]) {     int index = s.pop();     res[index] = prices[index] - prices[i];    }    s.push(i);         }         return res;     } } <\/code><\/pre>\n
\u66f4\u591a\u8bed\u8a00\u4ee3\u7801\u53c2\u89c1\uff1ahttps:\/\/www.lintcode.com\/problem\/final-discounted-price\/?utm_source=sc-v2ex-fks<\/p>\n<\/p><\/div>\n
 \u5927\u4f6c\u6709\u8a71\u8aaa<\/b> (1<\/span>)        <\/div>\n
 <\/div>\n<\/p><\/div>\n<\/p><\/div>\n
    \n
  • \n
    \n
    \n
     \u8cc7\u6df1\u5927\u4f6c : orangey <\/span>  <\/div>\n
     <\/i>            <\/span> <\/div>\n<\/p><\/div>\n
                                                                 \u4e0d\u61c2\u7b97\u6cd5\uff0c\u60f3\u95ee\u4e00\u4e0b \u8fd9\u4e2a\u7528\u4e8c\u5206\u4e5f\u53ef\u4ee5\u505a\u5427\uff1f                                                            <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n","protected":false},"excerpt":{"rendered":"
    [leetcode\/lintcod…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[],"tags":[],"_links":{"self":[{"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts\/125836"}],"collection":[{"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=125836"}],"version-history":[{"count":0,"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts\/125836\/revisions"}],"wp:attachment":[{"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=125836"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=125836"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=125836"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}