{"id":1946,"date":"2016-04-04T16:52:20","date_gmt":"2016-04-04T08:52:20","guid":{"rendered":"http:\/\/boweihe.me\/?p=1946"},"modified":"2016-04-04T16:52:20","modified_gmt":"2016-04-04T08:52:20","slug":"leetcode-239-sliding-window-maximum","status":"publish","type":"post","link":"https:\/\/dayandcarrot.space\/?p=1946","title":{"rendered":"LeetCode 239. Sliding Window Maximum"},"content":{"rendered":"

\u9898\u76ee<\/h3>\n

Given an array nums<\/i>, there is a sliding window of size k<\/i> which is moving from the very left of the array to the very right. You can only see the k<\/i> numbers in the window. Each time the sliding window moves right by one position.
\nFor example,
\nGiven nums<\/i> = [1,3,-1,-3,5,3,6,7]<\/code>, and k<\/i> = 3.<\/p>\n

Window position                Max\n---------------               -----\n[1  3  -1] -3  5  3  6  7       3\n 1 [3  -1  -3] 5  3  6  7       3\n 1  3 [-1  -3  5] 3  6  7       5\n 1  3  -1 [-3  5  3] 6  7       5\n 1  3  -1  -3 [5  3  6] 7       6\n 1  3  -1  -3  5 [3  6  7]      7\n<\/pre>\n
Therefore, return the max sliding window as [3,3,5,5,6,7]<\/code>.<\/p>\n
\u601d\u8def<\/h3>\n
\u53c8\u662f\u300a\u5251\u6307Offer\u300b\u7684\u539f\u9898\uff08#65\uff09\uff0c\u5927\u81f4\u8bb2\u4e00\u4e0b\u601d\u8def\u5427\u3002
\n\u601d\u8def\u6765\u6e90\u4e8e\u4e4b\u524d\u505a\u8fc7\u7684\u4e00\u9053\u9898\uff0c\u662f\u8981\u6c42\u8bbe\u8ba1\u4e00\u4e2a\u6808\uff0c\u53ef\u4ee5\u7528O(1)\u65f6\u95f4\u627e\u5230\u6808\u4e2d\u6700\u5927(\u6700\u5c0f)\u5143\u7d20\u7684\u3002\u5f53\u65f6\u7684\u65b9\u6cd5\u662f\uff0c\u53e6\u8f9f\u4e00\u4e2a\u6808\uff0c\u8bb0\u5f55\u53ef\u80fd\u4f1a\u6539\u53d8\u6700\u5927\u503c\u7684\u90a3\u4e9b\u503c\uff08\u53ef\u4ee5\u79f0\u4ed6\u4eec\u4e3a\u5173\u952e\u503c\uff09\uff0c\u5f53\u8fd9\u5f39\u51fa\u7684\u6808\u9876\u5143\u7d20\u6070\u597d\u662f\u8fd9\u4e9b\u503c\u7684\u65f6\u5019\uff0c\u628a\u5173\u952e\u503c\u6808\u9876\u7684\u5143\u7d20\u4e5f\u5f39\u51fa\u3002\u8fd9\u5c31\u76f8\u5f53\u4e8e\u505a\u4e86\u201c\u64a4\u9500\u201d\u64cd\u4f5c\uff0c\u8fd9\u65f6\u5173\u952e\u503c\u6808\u9876\u7684\u65b0\u5143\u7d20\u4e5f\u5c31\u662f\u76ee\u524d\u7684\u6700\u5927\u503c\u4e86\u3002
\n\u5047\u8bbe\u6211\u4eec\u7528\u4e00\u4e2a\u5bb9\u5668\u5b58\u653e\u90a3\u4e9b\u53ef\u80fd\u6210\u4e3a\u6700\u5927\u503c\u7684\u5143\u7d20\uff0c\u90a3\u7ef4\u62a4\u5b83\u8fc7\u7a0b\u5c31\u53d1\u751f\u5728\u5411\u540e\u79fb\u52a8\u7a97\u53e3\u8bfb\u5165\u4e00\u4e2a\u65b0\u5143\u7d20a[i]\u65f6\uff0c\u4e3b\u8981\u7684\u60f3\u6cd5\u6709\u4e24\u6b65\uff1a<\/p>\n
    \n
  • \u5982\u679ca[i]\u6bd4\u5bb9\u5668\u4e2d\u90a3\u4e9b\u6392\u5728\u5b83\u524d\u9762\u7684\uff08\u5148\u524d\u8bfb\u5165\u7684\uff09\u5143\u7d20\u5927\uff0c\u7531\u4e8ea[i]\u7684\u5b58\u6d3b\u65f6\u95f4\u80af\u5b9a\u6bd4\u8001\u4e00\u8f88\u4eec\u6765\u7684\u957f\uff0c\u56e0\u6b64\u524d\u9762\u90a3\u4e9b\u6bd4\u5b83\u7684\u503c\u8fd8\u5c0f\u7684\u5143\u7d20\u5c31\u53ef\u4ee5\u5220\u53bb\u4e86\uff1b<\/li>\n
  • \u5220\u53bb\u90a3\u4e9b\u201c\u8fc7\u6c14\u201d\u7684\u5143\u7d20\uff0c\u4e5f\u5c31\u662f\u76ee\u524d\u5df2\u7ecf\u4e0d\u5728\u7a97\u53e3\u4e2d\u7684\u90a3\u4e9b\u5143\u7d20\uff1b<\/li>\n<\/ul>\n
    \u6bcf\u632a\u52a8\u4e00\u4e0b\uff0c\u53ef\u4ee5\u5f97\u77e5\u5f53\u524d\u7a97\u53e3\u6700\u5927\u7684\u5143\u7d20\u80af\u5b9a\u5c31\u662f\u5728\u5bb9\u5668\u6700\u524d\u5934\u7684\uff08\u53ef\u80fd\u662f\u8fd8\u6ca1\u201c\u8fc7\u6c14\u201d\u8001\u5927\uff09\uff0c\u540e\u9762\u6392\u7740\u4e00\u4e32\u8001\u5927\u6302\u6389\u540e\u60f3\u5f53\u8001\u5927\u7684\u5143\u7d20
    \n\u7531\u4e8e\u6309\u7167\u65f6\u95f4\u987a\u5e8f\uff0c\u201c\u8fc7\u6c14\u201d\u5143\u7d20\u5728\u5bb9\u5668\u7684\u5f00\u5934\uff0c\u800c\u6211\u4eec\u53c8\u8981\u4ece\u5bb9\u5668\u7684\u672b\u5c3e\u5f00\u59cb\u627e\u90a3\u4e9b\u6bd4a[i]\u5c0f\u7684\u5143\u7d20\uff0c\u56e0\u6b64\u6709\u8fd9\u4e48\u4e24\u4e2a\u91cd\u8981\u51b3\u5b9a\uff1a<\/p>\n
      \n
    1. \u4f7f\u7528\u53cc\u7aef\u961f\u5217\u5b58\u653e\u5019\u9009\u5143\u7d20\uff1a\u56e0\u4e3a\u6211\u4eec\u8981\u65b9\u4fbf\u5730\u64cd\u4f5c\u6570\u7ec4\u7684\u9996\u672b\u9879\uff1b<\/li>\n
    2. \u961f\u5217\u4e2d\u5b58\u653e\u5143\u7d20\u7684\u5e8f\u53f7\u800c\u4e0d\u662f\u503c\uff1a\u8fd9\u662f\u56e0\u4e3a\u6211\u4eec\u8981\u5224\u65ad\u54ea\u4e9b\u5143\u7d20\u5df2\u7ecf\u6ed1\u51fa\u7a97\u53e3\u4e86\uff0c\u5982\u679c\u5b58\u50a8\u503c\u7684\u8bdd\uff0c\u6bcf\u6b21\u8fd8\u5f97\u91cd\u65b0\u5230\u539f\u5e8f\u5217\u91cc\u627e\u4f4d\u7f6e\uff1b<\/li>\n<\/ol>\n
      \u6574\u4e2a\u65b9\u6cd5\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u662fO(n)\uff0c\u7a7a\u95f4\u590d\u6742\u5ea6\u5e94\u8be5\u4e5f\u662fO(n)<\/p>\n
      \u4ee3\u7801<\/h3>\n
      class Solution {\npublic:\n    vector<int> maxSlidingWindow(vector<int>& nums, int k) {\n        int numSz = nums.size();\n        vector<int> results;\n        if(numSz <= 0 || k > numSz){\n            return results;\n        }\n        deque<int> working;\n        \/\/Init deque\n        for(int i=0; i<k; i++){\n            while(!working.empty() && nums[i]>=nums[working.back()]){\n                working.pop_back();\n            }\n            working.push_back(i);\n        }\n        results.push_back(nums[working.front()]);\n        \/\/Interate through remaining nums\n        for(int i=k; i<numSz; i++){\n            while(!working.empty() && working.front() <= (i-k)){\n                working.pop_front(); \/\/Remove the out-of-window elements\n            }\n            while(!working.empty() && (nums[i]>=nums[working.back()])){\n                working.pop_back();  \/\/Remove the smaller elements\n            }\n            working.push_back(i);\n            results.push_back(nums[working.front()]);\n        }\n        return results;\n    }\n};<\/pre>\n
       <\/p>\n","protected":false},"excerpt":{"rendered":"
      \u9898\u76ee Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. For example, Given nums = [1,3,-1,-3,5,3,6,7], and k […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[36,66],"class_list":["post-1946","post","type-post","status-publish","format-standard","hentry","category-study","tag-deque","tag-leetcode-oj"],"_links":{"self":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/1946","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1946"}],"version-history":[{"count":0,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/1946\/revisions"}],"wp:attachment":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1946"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1946"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1946"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}