刷题总结记录

目录

一、单调栈

1.1 单调栈介绍

1.2 代表题目

LeetCode84：柱状图中的最大矩形

LeetCode739：每日温度

LeetCode503：下一个更大元素

LeetCode85：最大矩形

LeetCode42：接雨水

LeetCode962：最大坡度

1.1 单调栈介绍

刷题笔记6（浅谈单调栈） - 知乎

单调栈的主要介绍参考以上文章，其典型应用是在数组中寻找第一个比自己大或者小的数，其经典代码如下所示：

//从数组input中寻找每个元素的下一个更大元素的坐标
vector nextExceed(vector &input) {
	vector result (input.size(), -1);//存坐标
	stack monoStack;
	for(int i = 0; i < input.size(); ++i) {	
		while(!monoStack.empty() && input[monoStack.top()] < input[i]) {
			result[monoStack.top()] = i;
			monoStack.pop();
		}
		monoStack.push(i);
	}
	return result;
}

1.2 代表题目 LeetCode496：下一个元素（进阶：LeetCode503）

题目：力扣

题目给定两个数组nums1与nums2，nums1是nums2的子集，需要找出nums1找那个元素在nums2中所在位置右侧第一个比自己大的数。此题是单调栈的简单应用：本人题解如下：

class Solution {
public:
    vector nextGreaterElement(vector& nums1, vector& nums2) {
        int m=nums1.size(),n=nums2.size();

        unordered_map nexBiger;//键值对分别为num2的值与其下一个更大值，初始化为-1
        for(int i=0;i maxstack;//单调递减栈，存下一个更大的值的坐标
        for(int i=0;inums2[maxstack.top()]){
                nexBiger[nums2[maxstack.top()]]=nums2[i];//把值放到哈希表
                maxstack.pop();
            }
            maxstack.push(i);
        }
        vector ans(m,-1);
        for(int i=0;i 
LeetCode84：柱状图中的最大矩形 
​​​​​​力扣：只要找到数字当前元素左右两边第一个比自己小的元素，就可以得到以当前元素为高的矩形的最大宽度。因此需要用两次单调栈
 
 
题解：
 
class Solution {
public:
    int largestRectangleArea(vector& heights) {
        //经典单调栈模型，一堆数中找到第一个比自己小/大的
        int ans=0,n=heights.size();
        stack minStack;
        vector right(n,n),left(n,-1);//表示第一个小的数的坐标，初始化为右边n，左边-1
        
        //右边第一个比自己小的数的坐标
        for(int i=0;i();//重新清空栈

        //左边第一个比自己小的数的坐标
        for(int i=n-1;i>=0;i--){
            while(!minStack.empty() && heights[i]< heights[minStack.top()]){                
                left[minStack.top()]=i;                
                minStack.pop();
            }
            minStack.push(i);            
        }

        for(int i=0;i 
 
 
LeetCode739：每日温度 
 
LeetCode85：最大矩形 
LeetCode42：接雨水 
LeetCode962：最大坡度