{"id":4537,"date":"2018-12-25T23:30:42","date_gmt":"2018-12-26T07:30:42","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=4537"},"modified":"2018-12-25T23:37:56","modified_gmt":"2018-12-26T07:37:56","slug":"leetcode-962-maximum-width-ramp","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/stack\/leetcode-962-maximum-width-ramp\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 962. Maximum Width Ramp"},"content":{"rendered":"\n

Given an array A<\/code> of integers, a ramp<\/em> is a tuple (i, j)<\/code> for which i < j<\/code> and A[i] <= A[j]<\/code>.  The width of such a ramp is j - i<\/code>.<\/p>\n\n\n\n

Find the maximum width of a ramp in A<\/code>.  If one doesn’t exist, return 0.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input: <\/strong>[6,0,8,2,1,5] 
Output: <\/strong>4 
Explanation: <\/strong> The maximum width ramp is achieved at (i, j) = (1, 5): A[1] = 0 and A[5] = 5. <\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input: <\/strong>[9,8,1,0,1,9,4,0,4,1] 
Output: <\/strong>7 
Explanation: <\/strong> The maximum width ramp is achieved at (i, j) = (2, 9): A[2] = 1 and A[9] = 1. <\/pre>\n\n\n\n
Note:<\/strong><\/p>\n\n\n\n
  1. 2 <= A.length <= 50000<\/code><\/li>
  2. 0 <= A[i] <= 50000<\/code><\/li><\/ol>\n\n\n\n
    Solution:\u00a0Stack<\/strong><\/h1>\n\n\n\n
    1. Using a stack to store start candidates’ (decreasing order) index<\/li>
    2. Scan from right to left, compare the current number with the one on the top of the stack, pop if greater.<\/li><\/ol>\n\n\n\n
      e.g. 
      A = [6<\/strong>,0<\/strong>,8,2,1,5]
      stack = [0, 1] => [6, 0] 
      cur: A[5] = 5, stack.top = A[1] = 0, ramp = 5, stack.pop()
      cur: A[4] = 1, stack.top = A[0] = 6
      cur: A[3] = 2, stack.top = A[0] = 6
      cur: A[2] = 8,  stack.top = A[0] = 6, ramp = 2, stack.pop()
      stack.isEmpty() => END<\/p>\n\n\n\n
      \n
      C++<\/h2>\n
      \n\n
      \n\/\/ Author: Huahua, running time: 44 ms\nclass Solution {\npublic:\n  int maxWidthRamp(vector& A) {\n    stack s;\n    for (int i = 0; i < A.size(); ++i)\n      if (s.empty() || A[i] < A[s.top()])\n        s.push(i);\n    int ans = 0;\n    for (int i = A.size() - 1; i >= 0; --i)\n      while (!s.empty() && A[i] >= A[s.top()]) {\n        ans = max(ans, i - s.top());\n        s.pop();\n      }\n    return ans;\n  }\n};\n<\/pre>\n\n<\/div>
      Python3<\/h2>\n
      \n\n
      \n# Author: Huahua, running time: 92 ms\nclass Solution:\n  def maxWidthRamp(self, A):\n    s = []\n    for i in range(len(A)):\n      if not s or A[i] < A[s[-1]]: s.append(i)\n    ans = 0\n    for i in range(len(A) - 1, -1, -1):\n      while s and A[i] >= A[s[-1]]:\n        ans = max(ans, i - s.pop())        \n    return ans\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
      Given an array A of integers, a ramp is a tuple (i, j) for which i < j and A[i] <= A[j].  The width of such a ramp is j – i. Find the maximum width…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[407],"tags":[413,52,447,177,180],"class_list":["post-4537","post","type-post","status-publish","format-standard","hentry","category-stack","tag-all-pairs","tag-binary-search","tag-decreasing","tag-medium","tag-stack","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4537","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=4537"}],"version-history":[{"count":5,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4537\/revisions"}],"predecessor-version":[{"id":4543,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4537\/revisions\/4543"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=4537"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=4537"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=4537"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}