{"id":10332,"date":"2025-04-11T08:44:23","date_gmt":"2025-04-11T15:44:23","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=10332"},"modified":"2025-04-11T08:50:12","modified_gmt":"2025-04-11T15:50:12","slug":"leetcode-2016-maximum-difference-between-increasing-elements","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/algorithms\/array\/leetcode-2016-maximum-difference-between-increasing-elements\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2016. Maximum Difference Between Increasing Elements"},"content":{"rendered":"\n<p>\u6570\u636e\u89c4\u6a21 n &lt;= 1000\u3002O(n<sup>2<\/sup>) \u7684\u7b97\u6cd5\u4e5f\u662f\u80fd\u8fc7\u7684\u3002<\/p>\n\n\n\n<p>\u65b9\u6cd51: Brute Force<\/p>\n\n\n\n<p>\u53cc\u91cd\u5faa\u73af\u679a\u4e3e\u6240\u6709\u7684(nums[i], nums[j])\u7684\u7ec4\u5408\u3002<\/p>\n\n\n\n<p>\u65f6\u95f4\u590d\u6742\u5ea6\uff1aO(n<sup>2<\/sup>)<br>\u7a7a\u95f4\u590d\u6742\u5ea6\uff1aO(1)<\/p>\n\n\n\n<pre lang=\"c++\">\nclass Solution {\npublic:\n  int maximumDifference(vector<int>& nums) {\n    const int n = nums.size();\n    int ans = 0;\n    for (int i = 0; i < n; ++i)\n      for (int j = i + 1; j < n; ++j)\n        ans = max(ans, nums[j] - nums[i]);\n    return ans ? ans : -1;\n  }\n};\n\n<\/pre>\n\n\n\n<p>\u65b9\u6cd52: \u7a7a\u95f4\u6362\u65f6\u95f4<\/p>\n\n\n\n<p>\u4f7f\u7528prefix sum\u7b97\u6cd5\uff0c\u9884\u5148\u8ba1\u7b97num[i] ~ nums[n-1]\u7684\u6700\u5927\u503c\uff0c\u5b58\u50a8\u5728right[i]\u4e2d\u3002<\/p>\n\n\n\n<p>\u65f6\u95f4\u590d\u6742\u5ea6\uff1aO(n)<br>\u7a7a\u95f4\u590d\u6742\u5ea6\uff1aO(n)<\/p>\n\n\n\n<pre lang=\"c++\">\nclass Solution {\npublic:\n  int maximumDifference(vector<int>& nums) {\n    const int n = nums.size();\n    int ans = 0;\n    vector<int> right(n, nums.back());\n    for (int i = n - 2; i >= 0; --i)\n      right[i] = max(right[i + 1], nums[i]);\n    for (int i = 0; i < n; ++i)\n      ans = max(ans, right[i] - nums[i]);\n    return ans ? ans : -1;\n  }\n};\n\n<\/pre>\n\n\n\n<p>\u65b9\u6cd53: Running Min<\/p>\n\n\n\n<p>\u4ece\u5de6\u5230\u53f3\u904d\u5386\uff0c\u8bb0\u5f55\u5f53\u524d\u4e3a\u6b62\u51fa\u73b0\u8fc7\u6700\u5c0f\u7684\u503c\u3002\u6bd4\u8f83 nums[i] - \u6700\u5c0f\u503c \u548c \u6700\u4f18\u89e3\u3002<\/p>\n\n\n\n<p>\u65f6\u95f4\u590d\u6742\u5ea6\uff1aO(n)<br>\u7a7a\u95f4\u590d\u6742\u5ea6\uff1aO(1)<\/p>\n\n\n\n<pre lang=\"c++\">\nclass Solution {\npublic:\n  int maximumDifference(vector<int>& nums) {\n    const int n = nums.size();\n    int ans = 0;\n    int smallest = nums[0];\n    for (int i = 1; i < n; ++i) {\n      ans = max(ans, nums[i] - smallest);\n      smallest = min(smallest, nums[i]);\n    }\n    return ans ? ans : -1;\n  }\n};\n\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u6570\u636e\u89c4\u6a21 n &lt;= 1000\u3002O(n2) \u7684\u7b97\u6cd5\u4e5f\u662f\u80fd\u8fc7\u7684\u3002 \u65b9\u6cd51: Brute Force \u53cc\u91cd\u5faa\u73af\u679a\u4e3e\u6240\u6709\u7684(nums[i], nums[j])\u7684\u7ec4\u5408\u3002 \u65f6\u95f4\u590d\u6742\u5ea6\uff1aO(n2)\u7a7a\u95f4\u590d\u6742\u5ea6\uff1aO(1) class Solution { public: int maximumDifference(vector&#038; nums) { const int n = nums.size(); int&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[184],"tags":[842],"class_list":["post-10332","post","type-post","status-publish","format-standard","hentry","category-array","tag-prefix-max","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/10332","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=10332"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/10332\/revisions"}],"predecessor-version":[{"id":10336,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/10332\/revisions\/10336"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=10332"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=10332"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=10332"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}