力扣（leetcode）题目总结——辅助栈篇
leetcode 经典题分类
- 链表
- 数组
- 字符串
- 哈希表
- 二分法
- 双指针
- 滑动窗口
- 递归/回溯
- 动态规划
- 二叉树
- 辅助栈
本系列专栏：点击进入 leetcode题目分类 关注走一波
前言：本系列文章初衷是为了按类别整理出力扣（leetcode）最经典题目，一共100多道题，每道题都给出了非常详细的解题思路、算法步骤、代码实现。很多同学刚开始刷题都是按照力扣顺序刷题，其实这样对新手不太适用，刷题效果也很不好。因为力扣题目顺序是随机的，并没有按照算法分类，导致同一类型的算法强化训练不够，最后刷完也是迷迷糊糊的。所以本系列文章就是来帮你完成算法分类，针对每种算法做强化训练，保证让你以后遇到题目直接秒杀！
有效的括号
【题目描述】
给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串s，判断字符串是否有效。
有效字符串需满足：
-
左括号必须用相同类型的右括号闭合；
-
左括号必须以正确的顺序闭合；
-
每个右括号都有一个对应的相同类型的左括号。
【输入输出实例】
示例 1：
输入：s = “()”
输出：true
示例 2：
输入：s = “()[]{}”
输出：true
示例 3：
输入：s = “(]”
输出：false
【算法思路】
先来分析一下，这里有三种不匹配的情况：
-
字符串里左方向的括号多余了，所以不匹配；
-
括号没有多余，但是括号的类型没有匹配上；
-
字符串里右方向的括号多余了，所以不匹配；
针对三种不匹配情况的代码：
-
第一种情况：已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false；
-
第二种情况：遍历字符串匹配的过程中，发现栈里没有要匹配的字符，所以return false；
-
第三种情况：遍历字符串匹配的过程中，栈已为空，没有匹配的括号，说明右括号没有找到对应的左括号，所以return false。
匹配成功的情况：
字符串遍历完之后，栈是空的，就说明全都匹配了。
技巧：
在遇到左括号时，不要让左括号本身入栈，而让相应的右括号入栈。则在遇到右括号匹配时，就只需要比较当前右括号和栈顶元素相不相等就可以了，比左括号入栈代码实现更简单。
【算法描述】
//括号匹配是使用辅助栈解决
bool isValid(string s)
{
stack<char> sta; //辅助栈
for(char ch : s) //遍历给定的括号字符串
{
switch(ch)
{
//技巧：遇到左括号就入栈其对应的右括号
case '(':
sta.push(')');
break;
case '[':
sta.push(']');
break;
case '{':
sta.push('}');
break;
default: //遇到右括号就检查是否匹配，检查本身与栈顶元素是否一样
if(sta.empty() || sta.top() != ch) //栈为空 或 本身与栈顶元素不一样，都说明括号不匹配
{
return false;
}
sta.pop(); //若一样，则出栈
}
}
return sta.empty(); //最后若有未出栈的元素说明，有不匹配的项
}
最长有效括号
【题目描述】
给你一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长有效(格式正确且连续)括号子串的长度。
【输入输出实例】
示例 1：
输入：s = “(()”
输出：2
示例 2：
输入：s = “)()())”
输出：4
示例 3：
输入：s = “()(()”
输出：2
示例 4：
输入：s = “”
输出：0
【算法思路】
创建一个大小为len的容器来表示各个括号的是否可匹配。用栈模拟一遍括号匹配，将所有无法匹配的括号的位置全部置1。例如："()(()“对应为[0, 0, 1, 0, 0]；再例如：”)()((())"的对应为[1, 0, 0, 1, 0, 0, 0, 0]。
经过这样的处理后，此题就变成了寻找最长的连续0的长度
【算法描述】
int longestValidParentheses(string s)
{
int len = s.size();
vector<int> v(len); //用来表示该位置的括号是否可匹配：无法匹配的括号的位置全部置1
stack<int> stk; //栈内存放括号下标
int maxLong = 0; //记录括号匹配的最大长度
for(int i = 0; i < len; i++)
{
if(s[i] == '(') //遇到左括号就入栈
{
stk.push(i);
}
else //遇到右括号就判断
{
if(stk.empty()) //多余的右括号是不需要的，标记1
{
v[i] = 1;
}
else //匹配成功
{
stk.pop();
}
}
}
while(!stk.empty()) //未匹配的左括号是不需要的，标记1
{
v[stk.top()] = 1;
stk.pop();
}
// 寻找标记与标记之间的最大长度，即找最长的连续的0的长度
int num = 0;
for(int i = 0; i < len; i++)
{
if(v[i] == 0)
{
num++;
}
else
{
maxLong = max(maxLong, num);
num = 0;
}
}
maxLong = max(maxLong, num);
return maxLong;
}
接雨水
【题目描述】
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
【输入输出实例】
示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
示例 2：
输入：height = [4,2,0,3,2,5]
输出：9
【算法思路】
首先，要知道单调栈是按照行方向来计算雨水，如图：
单调栈内元素的顺序：从栈头到栈底的顺序应该是从小到大的顺序。因为一旦发现要添加的柱子高度大于栈顶元素，此时就出现凹槽了，栈头元素就是凹槽底部的柱子，栈头第二个元素就是凹槽左边的柱子，而添加的元素就是凹槽右边的柱子。如图：
因为长就是通过柱子的高度来计算，宽是通过柱子之间的下标来计算，通过长*宽来计算雨水面积，所以栈中应该存放下标，计算的时候用下标对应的柱子高度即可。
算法过程就是：用单调栈不断入栈每个柱子对应的下标，当要入栈的柱子高度大于栈顶元素时，要先将元素出栈保留，即为凹槽的底部bottom。此时的栈顶元素为凹槽左边的柱子left，要入栈的柱子为凹槽右边的柱子right。则可算出这个凹槽中盛放水的高度：
rainHeight = min(height[left], height[right]) - height[temp];
宽度为：rainWidth = right - left - 1;
则可算出该凹槽中盛放水的体积，根据上述操作遍历(不断入栈出栈)完每根柱子，将得到的雨水量相加起来即可。
【算法描述】
//双指针法(超时)
int trap(vector<int>& height)
{
int len = height.size();
int sum = 0; //记录接的雨水
for(int i = 1; i < len - 1; i++) //遍历每列(除第一列和最后一列，因为它们不会接雨水)
{
int maxLeft = 0; //左边最高柱子的高度
int maxRight = 0; //右边最高柱子的高度
for(int left = i - 1; left >= 0; left--) //找左边最高柱子
{
maxLeft = max(maxLeft, height[left]);
}
for(int right = i + 1; right < len; right++) //找右边最高柱子
{
maxRight = max(maxRight, height[right]);
if(maxRight > maxLeft) //因为最后要取两者最小，所以只要超过左边最高柱子，直接退出
{
break;
}
}
int rainHeight = min(maxLeft, maxRight) - height[i]; //计算雨水高度
sum += (rainHeight > 0) ? rainHeight : 0;
}
return sum;
}
//动态规划——相当于双指针法，只是用动态规划来提前求出每个柱子的最大左边柱子和最大右边柱子
int trap(vector<int>& height)
{
int len = height.size();
int sum = 0; //记录接的雨水
vector<int> maxLeft(len); //记录第i列左边柱子最大高度
vector<int> maxRight(len); //记录第i列右边柱子最大高度
maxLeft[0] = height[0]; //初始化
maxRight[len-1] = height[len-1];
//记录每个柱子左边柱子最大高度
for(int i = 1; i < len-1; i++)
{
maxLeft[i] = max(maxLeft[i-1], height[i]);
}
//记录每个柱子右边柱子最大高度
for(int i = len-2; i > 0; i--)
{
maxRight[i] = max(maxRight[i+1], height[i]);
}
//遍历每列算雨水量再求和
for(int i = 1; i < len - 1; i++)
{
int rainHeight = min(maxLeft[i-1], maxRight[i+1]) - height[i];
sum += (rainHeight > 0) ? rainHeight : 0;
}
return sum;
}
//单调栈
int trap(vector<int>& height)
{
int sum = 0; //记录接的雨水
stack<int> s; //单调栈
s.push(0);
for(int i = 1; i < height.size(); i++)
{
//如果栈不空并且当前指向的高度大于栈顶高度就一直循环
while(!s.empty() && height[i] > height[s.top()])
{
int temp = height[s.top()]; //取出要出栈的元素
s.pop(); //出栈
if(!s.empty()) //出栈一个后如果栈不为空，就开始算雨水
{
int rainHeight = min(height[i], height[s.top()]) - temp; //计算雨水高度：-temp相当于是减去i和s.top()两列构成容器的底部柱子的高度
int rainWidth = i - s.top() - 1; //雨水宽度
sum += rainHeight * rainWidth; //雨水量
}
}
s.push(i); //每根柱子要入栈
}
return sum;
}
柱状图中最大的矩形
【题目描述】
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为1。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
【输入输出实例】
示例 1:
输入：heights = [2,1,5,6,2,3]
输出：10
示例 2：
输入：heights = [2,4]
输出：4
【算法思路】
本题目与42、接雨水非常相似，也是有三种方法，如下：
(1)双指针法和动态规划
接雨水是找每列中左侧最高的柱子和右侧最高的柱子。找到后该列的雨水高度可得到，宽度为1，就可得到该列的雨水量，再把每列的雨水累加起来即可；
本题是找每个柱子左右两侧最后一个大于等于该柱子高度的柱子。找到后勾勒出来的矩形的宽度为左右两侧这两列的下标差，高度就是本列柱子的高度，则可计算出本列勾勒出来最大矩形的面积，再把每列勾勒出来的矩形面积求出来，再找最大。
(2)单调栈
接雨水是找每个柱子左右两边第一个大于该柱子高度的柱子，而本题是找每个柱子左右两边第一个小于该柱子的柱子。所以从栈头到栈底的顺序应该是从大到小的顺序。
如上图，可知只有栈里从大到小的顺序，才能保证栈顶元素找到左右两边第一个小于栈顶元素的柱子。
其实就是栈顶和栈顶的下一个元素以及要入栈的三个元素组成了我们要求最大面积的高度和宽度。其中栈顶元素为矩形高度，栈顶的下一个元素以及要入栈的元素的下标构成了矩阵的宽度。
其实可以把这个过程想象成锯木板，如果木板都是递增的那我很开心不用管。如果突然遇到一块木板 i 矮了一截，那我就先找之前最戳出来的一块（其实就是第 i-1 块），计算一下这个木板单独的面积，然后把它锯成次高的，这是因为我之后的计算都再也用不着这块木板本身的高度了。再然后如果发现次高的仍然比现在这个 i 木板高，那我继续单独计算这个次高木板的面积（应该是第 i-1 和 i-2 块组成的木板），再把它俩锯短。直到发现不需要锯就比第 i 块矮了，那我继续开开心心往右找更高的。当然为了避免到了最后一直都是递增的，所以可以在最后加一块高度为0的木板。
这个算法的关键点是把那些戳出来的木板早点单独拎出来计算，然后就用不着这个值了。
【算法描述】
//双指针法——超时
int largestRectangleArea(vector<int>& heights) {
int n = heights.size();
int maxArea = 0; //记录矩形的最大面积
for(int i = 0; i < n; i++) //遍历每根柱子
{
int left = i - 1;
int right = i + 1;
//找左边最后一个大于等于heights[i]的下标
for(; left >= 0; left--)
{
if(heights[left] < heights[i])
{
break;
}
}
//找右边最后一个大于等于heights[i]的下标
for(; right < n; right++)
{
if(heights[right] < heights[i])
{
break;
}
}
int height = heights[i]; //矩形高度
int width = right - left - 1; //矩形宽度
maxArea = max(maxArea, height*width); //计算最大面积
}
return maxArea;
}
//动态规划
int largestRectangleArea(vector<int>& heights)
{
int n = heights.size();
int maxArea = 0; //记录矩形的最大面积
vector<int> left(n);
vector<int> right(n);
left[0] = -1; //初始化
right[n-1] = n;
//记录每个柱子左边第一个高度小于该柱子的下标
for(int i = 1; i < n; i++)
{
int index = i - 1;
while(index >= 0 && heights[i] <= heights[index])
{
index = left[index]; //动态规划更新，上一次已经求过，不用重复求
}
left[i] = index;
}
//记录每个柱子右边第一个高度小于该柱子的下标
for(int i = n - 2; i >= 0; i--)
{
int index = i + 1;
while(index < n && heights[i] <= heights[index])
{
index = right[index]; //动态规划更新，上一次已经求过，不用重复求
}
right[i] = index;
}
//计算矩形的最大面积
for(int i = 0; i < n; i++)
{
int height = heights[i]; //矩形高度
int width = right[i] - left[i] - 1; //矩形宽度
maxArea = max(maxArea, height*width); //计算最大面积
}
return maxArea;
}
//单调栈
int largestRectangleArea(vector<int>& heights) {
heights.insert(heights.begin(), 0); //数组头部加入元素0
heights.push_back(0); //数组尾部加入元素0
int maxArea = 0; //记录矩形的最大面积
stack<int> s; //单调栈(递减)
s.push(0);
for(int i = 1; i < heights.size(); i++) //遍历各柱子
{
while(heights[i] < heights[s.top()])
{
int height = heights[s.top()]; //矩形高度
//int width = i - s.top(); //这时得到的矩形宽度没有把之前出栈的柱子宽度算上，因为之前出栈的柱子高度肯定大于它后面的柱子高度，所以才被出栈，那么要把前面已出栈的柱子宽度也要算上
s.pop();
int width = i - s.top() - 1; //矩形宽度：把前面已出栈的宽度也要算上
maxArea = max(maxArea, height*width); //计算最大面积
}
s.push(i);
}
return maxArea;
}
恭喜你全部读完啦！古人云：温故而知新。赶紧收藏关注起来，用之前再翻一翻吧~
📣推荐阅读
C/C++后端开发面试总结：点击进入 后端开发面经 关注走一波
C++重点知识：点击进入 C++重点知识 关注走一波
力扣（leetcode）题目分类：点击进入 leetcode题目分类 关注走一波
原文地址：https://blog.csdn.net/weixin_46571171/article/details/143808910
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！