首页 > 其他分享 >leetcode 42 单调栈解法

leetcode 42 单调栈解法

时间:2024-01-30 14:58:34浏览次数:30  
标签:tempheight temp int 复杂度 42 low ans leetcode 解法

Problem: 42. 接雨水

目录

思路

作为自己独立完成的第一道困难题,我觉得有必要纪念一下。就是单调栈的思路,不过需要减去栈中的每一项才是雨水的体积。最后一个因为不是柱子,所以在结束循环时可能会出现栈未空的情况,需要倒着再考虑一遍。

解题方法

遇到比当前大的就改变low,然后计算雨水含量,否则就入栈,栈未空时倒着再考虑一遍

复杂度

时间复杂度:

添加时间复杂度, 示例: \(<O(3n)\)

空间复杂度:

\(O(n)\)

Code

class Solution {
public:
    int trap(vector<int>& height) {
        stack<int> temp;
        int n=height.size();
        int low=0,fast=1,ans=0;
        if(n<=1) return 0;
        while (fast<n)
        {
          if(height[fast]<height[low]){
            temp.push(height[fast]);
            fast++;
          }
          else{
            int s=temp.size();
            int tempheight=s*height[low];
            while (!temp.empty())
            {
              int a=temp.top();
              temp.pop();
              tempheight-=a;
            }
            ans+=tempheight;
            low=fast;
            fast++;
          }
        }
        if(!temp.empty()){
          int a=0,count=0,tempheight=0;
          bool judge=false;
           while (!temp.empty())
        {
          if(temp.top()>=a) {
            ans=ans+tempheight+a*count;
            count=0;
            tempheight=0;
            a=temp.top();
            }
          else {count++;tempheight-=temp.top();}
          temp.pop();
          if(temp.size()==0&&judge==false) {temp.push(height[low]);judge=true;}//这里因为栈前面是有高柱子的,所以要把low按进去再考虑一遍
        }
        }
        return ans;
    }
};

标签:tempheight,temp,int,复杂度,42,low,ans,leetcode,解法
From: https://www.cnblogs.com/oxidationreaction/p/17997087

相关文章

  • LeetCode 2808 使循环数组所有元素相等的最少秒数
    题目描述原题链接:2808.使循环数组所有元素相等的最少秒数解题思路每次变化可以选择变成前一个元素或后一个元素,包括[0]和[n-1]的转化;换个角度思考,每秒最多可以有两个不同元素nums[i-1]和nums[i+1]变化成nums[i]元素;假设nums[i]元素只出现一次,想要将所有元素同化那么......
  • 代码随想录算法训练营第六天 |242. 有效的字母异位词 349. 两个数组的交集 202. 快乐
    1.两数之和 已解答简单 相关标签相关企业 提示 给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是,数组中同......
  • A+B问题1+105种解法
    个人写法应该没有更短的了吧,挑战世界最短a,b;main(){scanf("%d%d",&a,&b);printf("%d",a+b);}要测试点这里以下转自\(AcWing\)=================原作者为Conan15。要测试点温馨提示:此题解适合人群为算法学习者,不那么适合语法基础课还没学完的学生为了不误导初学者先......
  • Leetcode刷题第五天-二分法-回溯
    215:第k个最大元素链接:215.数组中的第K个最大元素-力扣(LeetCode)em~~怎么说呢,快速选择,随机定一个目标值,开始找,左边比目标小,右边比目标大,左右同时不满足时,交换左右位置,直到左指针比右指针大,交换目标和右指针位置的值,此时右指针位置即时目标值的在排序好数组中的位置,如果k在右......
  • Gym104270E Kawa Exam
    题意简述有\(n\)道题,每道题有\(10^5\)个选项,其中选项\(a_i\)是正确的。再给定\(m\)条限制\(u_i,v_i\),表示题目\(u_i,v_i\)必须要选择相同的选项。对于\(m\)条限制,求出若去掉这条限制,最多能回答多少问题。多组数据。\(n,m,a_i\le10^5,\sumn,\summ\le10^6\)。......
  • leetcode--98. 验证二叉搜索树(bfs)
    记录13:502024-1-28https://leetcode.cn/problems/validate-binary-search-tree/想岔方向了,想的太复杂了。首先思路是每个root节点必须大于左子树的最大节点,小于右边子树的最小节点。我的做法是记录下叶子节点,因为左边叶子节点的集合(vector)的最后一个节点为左子树的最大值......
  • CF1423G Growing flowers题解
    考虑每种颜色的贡献,用总数\(n-k+1\)减去没有贡献到的(极长连续段长度为\(len\)时),贡献为\(\max(len-k+1,0)\),所以考虑用\(\text{ODT}\)维护所有颜色的连续段。具体的,维护一个大的\(ODT\)存储所有连续段,再对每个颜色存储自己的连续段,用\(\text{BIT}\)维护每个长度的极长......
  • 142. 环形链表 II(中)
    目录题目题解:双指针题目给定一个链表的头节点head,返回链表开始入环的第一个节点。如果链表无环,则返回null。如果链表中有某个节点,可以通过连续跟踪next指针再次到达,则链表中存在环。为了表示给定链表中的环,评测系统内部使用整数pos来表示链表尾连接到链表中的位置(索......
  • 代码随想录算法训练营第四天| 24. 两两交换链表中的节点 19.删除链表的倒数第N个节
    24.两两交换链表中的节点给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。题目链接:24.两两交换链表中的节点-力扣(LeetCode)建议画图,会更清晰一些。同时注意交换问题要用两个临时节点。class......
  • P4342 [IOI1998] Polygon
    原题链接题解最近做的题目有点多,感觉没什么好讲的,某个最大值一定是由连续区间上的节点操作后得来的\(Code\)#include<bits/stdc++.h>usingnamespacestd;intf[105][105][2];intmain(){memset(f,-0x3f3f3f,sizeoff);intn;cin>>n;charop[105];......