4 下一个更大元素II

LeetCode:下一个更大元素II
跑两遍几可以了，自然会保证循环。

class Solution {
public:vector nextGreaterElements(vector& nums) {//跑两遍以保证覆盖vector result(nums.size(),-1);stack stk;stk.push(0);for(int i=1;i<2*nums.size()-1;++i){int index=i%(nums.size());while(!stk.empty() && nums[stk.top()]result[stk.top()]=nums[index];stk.pop();}stk.push(index);}return result;}
};

5 接雨水

LeetCode:接雨水
超级超级经典的题目，能用双指针+动态规划解决，也能用单调栈解决。

• 单调栈的思想是横着装满雨水，维持一个栈底到栈顶降序的单调栈，一旦出现递增元素，说明栈顶 < 遍历元素 && 栈顶 < 栈顶之下的元素，即栈顶为洼点。计算由两边与洼点所组成的谷地的面积。
• 双指针+动态规划的思想是竖着装满雨水，每一个列的雨水量，其宽度必然为1，其高度由【自身高度】与【左边最高值 和 右边最高值 中的最小值】的差决定，因此使用动态规划，事先记录每个列的【左最高值】和【右最高值】。

单调栈

class Solution {
public:int trap(vector& height) {if(height.size()<=2)return 0;//单调栈,从栈底->栈顶为降序//一旦比栈顶大，说明toptop，top为一个洼点，可以承接雨水stack stk;stk.push(0);int count=0;for(int i=1;i//横着装水while(!stk.empty() && height[stk.top()]<=height[i]){//洼点int mid=stk.top();stk.pop();if(!stk.empty()){//左侧柱int left=stk.top();int h=min(height[left],height[i])-height[mid];//此处使用i和left计算宽度int w=i-left-1;count+=h*w;}}stk.push(i);}return count;}
};

双指针+动态规划

class Solution {
public:int trap(vector& height) {if(height.size()<=2)return 0;//双指针，每一列的雨水量=max ( min(LeftHeight,RightHeight) - Height )vector leftHeight(height.size(),height[0]);vector rightHeight(height.size(),height.back());//每一列i的左侧最高值for(int i=1;i=0;--i)rightHeight[i] = max(rightHeight[i+1],height[i]);//求雨水量int rain_count=0;//显然头尾不会有雨水for(int i=1;iint diff_h=min(leftHeight[i],rightHeight[i])-height[i];rain_count+=max(0,diff_h);}return rain_count;}
};

6 柱状图中最大的矩形

LeetCode:柱状图中最大的矩形
与接雨水没有太多的区别，比较关键地在于需要记录的是索引而不是值。

• 在单调栈的使用中，必须明确遇到递减元素时，去计算从栈顶（此时遍历元素尚未入栈）到（大于遍历元素）之间[ 所有元素 ] 到达 [ 遍历元素 ]位置所形成的矩形。
  为了保证最后一个元素向前构造矩形和一定能找到左边界，分别要在末尾和头部添加0，扩充数组。
• 当然使用双指针+动态规划会更清晰一些，但事实上也隐晦地蕴含了对于头尾的处理，并且类似于KMP算法，使用了启发式搜索，跳过了大量无意义的遍历。

单调栈

class Solution {
public:int largestRectangleArea(vector& heights) {//单调栈，维护一个底->顶的升序单调栈//heights头尾都加入0heights.insert(heights.begin(),0);heights.push_back(0);//进行单调栈维护int size=heights.size();stack stk;stk.push(0);int max_area=0;for(int i=1;iif(heights[i]>heights[stk.top()])stk.push(i);else if(heights[i]==heights[stk.top()]){stk.push(i);}else{while(!stk.empty() && heights[i]int mid=stk.top();stk.pop();if(!stk.empty()){int left=stk.top();int right=i;int h=heights[mid];int w=right-left-1;max_area=max(max_area,h*w);}}stk.push(i);}}return max_area;}
};

双指针+动态规划

class Solution {
public:int largestRectangleArea(vector& heights) {//双指针，记录自己【左边第一个比自己小的】和【右边第一个比自己小的】int size=heights.size();vector leftIndex(size);vector rightIndex(size);//初始化左边第一个比自己小的坐标leftIndex[0]=-1;for(int i=1;iint t=i-1;//height[t] >= heights[i]，说明t不满足条件，需要向前寻找//必然地，在leftIndex[t]+1 ~ t之间的数index，由于必然height[index]>=height[t]>=heights[i]//所以必须从leftIndex[t]开始向前寻找，以此类推while(t>=0 && heights[t]>=heights[i])t=leftIndex[t];leftIndex[i]=t;}//同理处理右侧rightIndex[size-1]=size;for(int i=size-2;i>=0;--i){int t=i+1;while(t=heights[i])t=rightIndex[t];rightIndex[i]=t;}int max_area=0;//开始处理数组for(int i=0;iint length = rightIndex[i] - leftIndex[i] - 1;max_area = max(max_area, length*heights[i]);}//返回结果return max_area;}
};

7 总结

Leetcode基础部分就到此为止了，可以说一句完结撒花了。
整整23篇，至少也是20天的努力，写Markdown对我而言既是一种负担，也是一种督促，但事实上，决不能沉溺于Leetcode的舒适圈，明天开始要好好地恶补计算机基础知识了。
之后这个系列估计只会偶尔更新了，可能明天会写一点背包问题的内容，主要是记录昨天看背包九讲的收获吧，引用一句其中很喜欢的一句话：失败从不是什么丢人的事，从失败中全无收获才是，前者是pratice，而后者才是failure。
——2023.3.7