欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

leetcode-42. 接雨水之单调栈

程序员文章站 2024-01-20 12:31:28
...

题目

leetcode-42. 接雨水之单调栈前天学习了一道单调栈的问题(拼接最大数),又找到一道类似方法的题目,而且也是hard难度的,说明这个单调栈是算法中比较难的点

方法一

想了很久u最后搞出一种时间复杂度为O(n2)的方法,是先找到数组中的最大值max,然后从1到max向上遍历,找出大于等于1,2,3…max的所有数,求他们的距离之和就是每一层可以装下的雨水!

class Solution {
public:
    int trap(vector<int>& height) {
        if(height.size() == 0)
            return 0;
        auto iter = max_element(height.begin(),height.end());
        int max_num = *iter;
        int sum = 0;
        for(int i=1;i<=max_num;i++){
            int pos = 0;
            int count = 0;
            for(int j=0;j<height.size();j++){
                if(height[j]>=i){
                    if(count == 0)
                        pos = j;
                    else{
                        sum += (j-pos-1);
                        pos = j;
                    }
                    count++;
                }
            }
        }
        return sum;
    }
};

很显然对于这种hard的题目这个方法是不可能不超时的~

方法二

一句话:找左右两边最大值中小者,减去本身高度,就是每个数对于的雨水量!

class Solution {
public:
    int trap(vector<int>& height) {
        if(height.size() == 0)
            return 0;
        vector<int> left(height.size(),0); 
        // left数组是用于记录每个数左边的最大值
        vector<int> right(height.size(),0);
        // right数组是用于记录每个数右边的最大值
        left[0] = height[0];
        right[height.size()-1] = height[height.size()-1];
        for(int i=1;i<height.size();i++)
            left[i] = max(left[i-1],height[i]);
        
        for(int i=height.size()-2;i>=0;i--)
            right[i] = max(right[i+1],height[i]);
        
        int sum = 0;
        for(int i=0;i<height.size();i++){
            int tmp = min(left[i],right[i]);
            tmp = max(0,tmp - height[i]);
            sum += tmp;
        }
        return sum;

    }
};

方法三

单调栈方法,维护递减的单调栈,但是这里用单调栈其实相对于方法二来说还是复杂了;
这里直接引用官方题解的解释:

我们在遍历数组时维护一个栈。如果当前的条形块小于或等于栈顶的条形块,我们将条形块的索引入栈,意思是当前的条形块被栈中的前一个条形块界定。如果我们发现一个条形块长于栈顶,我们可以确定栈顶的条形块被当前条形块和栈的前一个条形块界定,因此我们可以弹出栈顶元素并且累加答案到ans 。

链接:https://leetcode-cn.com/problems/trapping-rain-water/solution/jie-yu-shui-by-leetcode/

class Solution {
public:
    int trap(vector<int>& height) {
        stack<int> s; 
        // 栈用于压入数的索引,方便计算距离
        int sum = 0;
        for(int i=0;i<height.size();i++){
            int water = 0;
            while(!s.empty() && height[s.top()]<height[i]){
                int top = height[s.top()];
                s.pop();
                if(s.empty())
                    break;
                int distance = i - s.top() - 1;
                int high = min(height[s.top()],height[i]) - top;
                water = water + distance*high;
            }
            s.push(i);
            sum += water;
        }
        return sum;

    }
};
相关标签: leetcode