leetcode962最大宽度坡

喜欢ヅ旅行 2022-10-05 06:57 222阅读 0赞

在这里插入图片描述
思路：单调栈 这个思路有点难想

  1. i<j，且 j - i 尽可能的大，那么i从左开始，j从右开始
  2. A[i] < = A[j]，使A[i]尽可能的小，从右向左进行遍历比较
  3. 从A[0]开始，存储严格单调递减的i。

  4. 反向扫描比较A[j]>A[s.top()]即栈顶元素值，满足条件就弹出，直至栈为空，满足条件时要记录j - i的最大值。

    int maxWidthRamp(vector& nums){ 

    1. vector<int> down;
    2. int r = 0;
    3. int len = nums.size();
    4. if(len==0||len==1)
    5.     return 0;
    6. int i;
    7. for(i=0;i<len;i++){ 
    8.     if(down.empty()){ 
    9.         down.push_back(i);
    10.     }
    11.     else if(nums[down.back()]>nums[i])
    12.         down.push_back(i);
    13. }
    14. for(i=len-1;i>=0;i--){ 
    15.     while (!down.empty()&&nums[down.back()]<=nums[i])
    16.     { 
    17.         int pos = down.back();
    18.         down.pop_back();
    19.         r = max(r,i-pos);
    20.     }
    22. }
    23. return r;

    }

发表评论

表情：
评论列表 （有 0 条评论，222人围观）

还没有评论，来说两句吧...

相关阅读