• 代码随想录打卡—day59—【单调栈】— 9.5 单调栈2


    1 503. 下一个更大元素 II

    503. 下一个更大元素 II

    for俩遍+vis访问数组+单调栈

    AC:

    1. class Solution {
    2. public:
    3. vector<int> nextGreaterElements(vector<int>& nums) {
    4. //for*2单调栈
    5. vector<int> ans(nums.size(),-1);
    6. stack<int>sk;
    7. vector<bool> vis(nums.size(),0);
    8. for(int i = 0,k = 0; k < 2*nums.size();k++,i++,i %= nums.size())
    9. {
    10. if(sk.empty() || nums[i] <= nums[sk.top()])
    11. {
    12. if(vis[i] == 0)
    13. sk.push(i);
    14. }
    15. else
    16. {
    17. while(!sk.empty() && nums[i] > nums[sk.top()] )
    18. {
    19. ans[sk.top()] = nums[i];
    20. vis[sk.top()] = 1;
    21. sk.pop();
    22. }
    23. if(vis[i] == 0)
    24. sk.push(i);
    25. }
    26. }
    27. return ans;
    28. }
    29. };

    看了题解:应该不加vis 直接重复加之前访问过的元素 也没事,原因是它还是值会被右边第一个大于自身的元素弹出 就是重复操作一次。确实,AC:

    1. class Solution {
    2. public:
    3. vector<int> nextGreaterElements(vector<int>& nums) {
    4. //for*2单调栈
    5. vector<int> ans(nums.size(),-1);
    6. stack<int>sk;
    7. for(int i = 0,k = 0; k < 2*nums.size();k++,i++,i %= nums.size())
    8. {
    9. if(sk.empty() || nums[i] <= nums[sk.top()])
    10. {
    11. sk.push(i);
    12. }
    13. else
    14. {
    15. while(!sk.empty() && nums[i] > nums[sk.top()] )
    16. {
    17. ans[sk.top()] = nums[i];
    18. sk.pop();
    19. }
    20. sk.push(i);
    21. }
    22. }
    23. return ans;
    24. }
    25. };

    2 42. 接雨水

    42. 接雨水

    【解法1:】自己写的双指针 就是逻辑不清晰,但也过了

    一开始的思路: lr一开始先找到非0元,然后r找到第一个>= height[l]的元素 ans+= ,l = r 重复或者r到头了结束 。但是这样不能处理样例。于是又想到 右边height.size()-1 至0 右边往左边重复一次,取两次最大值。 过得了样例 但是还是不对。处理不了 [6,4,2,0,3,2,0,3,1,4,5,3,2,7,5,3,0,1,2,1,3,4,6,8,1,3] 类似的样例

    最终思路:所以还是要左到右一次过 ,并且在最后一个高点找不到右匹配时候,右往左(左边界为新的高点l)再来一次。

    AC代码:不可思议,完全一个脑子想出ac的第一道困难题,泰酷辣!

    1. class Solution {
    2. public:
    3. int trap(vector<int>& height)
    4. {
    5. //双指针
    6. int l = 0;
    7. int r = 0;
    8. // 思路: lr一开始先找到非0元,然后r找到第一个>= height[l]的元素 ans+= ,l = r 重复或者r到头了结束
    9. // r到头了还是存在没一段没处理的部分,所以所以需要以当前的l作为左边界 右边往左边再来一次
    10. while(l < height.size() && height[l] == 0 )l++;
    11. r = l+1;
    12. int ans1 = 0;
    13. int tmp1 = 0;
    14. while(l < height.size())
    15. {
    16. while( r < height.size() && height[r] < height[l])
    17. {
    18. tmp1 += (height[l] - height[r]);
    19. r++;
    20. }
    21. if(r < height.size())
    22. {
    23. ans1 += tmp1;
    24. tmp1 = 0;
    25. l = r;
    26. r++;
    27. }
    28. if(r == height.size()) // 开始反向走
    29. {
    30. int end_l = l;
    31. l = height.size() - 1;
    32. r = l - 1;
    33. tmp1 = 0;
    34. while(r >= end_l )
    35. {
    36. while(r >= end_l && height[r] < height[l])
    37. {
    38. tmp1 += (height[l] - height[r]);
    39. r--;
    40. }
    41. if(r >= end_l)
    42. {
    43. ans1 += tmp1;
    44. tmp1 = 0;
    45. l = r;
    46. r--;
    47. }
    48. }
    49. break;
    50. }
    51. }
    52. cout << ans1 << endl;
    53. return ans1;
    54. }
    55. };

    【解法2:】双指针第2版-->左右两个数组大法

    AC:

    1. class Solution {
    2. public:
    3. int trap(vector<int>& height)
    4. {
    5. //双指针第2版-->左右两个数组大法
    6. /*
    7. 关键:
    8. 把问题转换成
    9. 每个格子应该的补充的高 是其左侧最高和右侧最高的min-当前高
    10. */
    11. vector<int> left(height.size()); // 元素i左侧最大的元素
    12. vector<int> right(height.size()); //元素i右侧最大的元素
    13. int left_max = 0;
    14. int right_max = 0;
    15. for(int i = 0; i < height.size();i++)
    16. {
    17. if(i != 0)left[i] = left_max;
    18. left_max = max(left_max,height[i]);
    19. }
    20. for(int i = height.size()-1; i >= 0;i--)
    21. {
    22. if(i != height.size()-1)right[i] = right_max;
    23. right_max = max(right_max,height[i]);
    24. }
    25. int ans = 0;
    26. for(int i = 0; i < height.size();i++)
    27. {
    28. if(i == 0 || i == height.size())continue;
    29. if(min(left[i],right[i]) > height[i])
    30. ans += (min(left[i],right[i])-height[i]);
    31. }
    32. return ans;
    33. }
    34. };

    【解法3:】单调栈做法

    AC:

    1. class Solution {
    2. public:
    3. int trap(vector<int>& height)
    4. {
    5. // 单调栈
    6. stack<int> sk;
    7. int ans = 0;
    8. sk.push(0); // 懒得多一个判断栈空的if
    9. for(int i = 1; i < height.size();i++)
    10. {
    11. if(height[i] < height[sk.top()])
    12. {
    13. sk.push(i);
    14. }
    15. else if(height[i] == height[sk.top()])
    16. {
    17. sk.pop();
    18. sk.push(i);
    19. }
    20. else
    21. {
    22. while(!sk.empty() && height[i] > height[sk.top()])
    23. {
    24. int tmp = sk.top();
    25. sk.pop();
    26. if(!sk.empty())
    27. {
    28. int h = min(height[i],height[sk.top()]) - height[tmp];
    29. int w = i - sk.top() - 1;
    30. ans += h*w;
    31. }
    32. }
    33. sk.push(i);
    34. }
    35. }
    36. return ans;
    37. }
    38. };

  • 相关阅读:
    WPF优秀组件推荐之Stylet(一)
    Pandas-02(描述性统计、函数的应用、重建索引、迭代)
    Java面向对象之接口和抽象类的区别一目了然
    ROS 话题通信理论模型
    流程设计的基本步骤
    机器学习之感知机原理及Python实现
    小狗避障-第14届蓝桥杯省赛Scratch中级组真题第4题
    python 集合
    【科技与狠活】如何利用Python绘制足球场
    免费的云产品
  • 原文地址:https://blog.csdn.net/weixin_60899084/article/details/132684416