万建站南昌,移动互联网开发前景,装修公司网站怎么建设,杭州室内设计培训【有效括号】
给定一个只包括 (#xff0c;)#xff0c;{#xff0c;}#xff0c;[#xff0c;] 的字符串 s #xff0c;判断字符串是否有效。
有效字符串需满足#xff1a;
左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的…【有效括号】
给定一个只包括 (){}[] 的字符串 s 判断字符串是否有效。
有效字符串需满足
左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。
思路
遇到左括号入栈遇到右括号弹一个出来看是否匹配全部走完看栈里是否还有没配对的左括号如果以上步骤中任意时刻出问题直接返回false都没出问题则返回true。
class Solution {
public:bool isValid(string s) {vectorchar stk;for (int i 0; i s.size(); i) {if (s[i] ( || s[i] { || s[i] [) {stk.push_back(s[i]);}if (s[i] )) {if (stk.empty()||stk.back() ! ( )return false;stk.pop_back();}if (s[i] }) {if (stk.empty()||stk.back() ! {)return false;stk.pop_back();}if (s[i] ]) {if (stk.empty()||stk.back() ! [)return false;stk.pop_back();}}return stk.empty();}
};
【最小栈】
设计一个支持 push pop top 操作并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。void push(int val) 将元素val推入堆栈。void pop() 删除堆栈顶部的元素。int top() 获取堆栈顶部的元素。int getMin() 获取堆栈中的最小元素。
思路
对于栈中任意元素在它出栈前比它更靠近栈底的元素是不可能发生变化的那么我们使用一个辅助栈记录当前元素及其下方所有元素中的最小值即可。
class MinStack {
public:stackint stk;stackint stk_min;MinStack() { stk_min.push(INT_MAX); }void push(int val) {stk.push(val);if (val stk_min.top())stk_min.push(val);elsestk_min.push(stk_min.top());}void pop() {if (!stk.empty()) {stk.pop();stk_min.pop();}}int top() { return stk.top(); }int getMin() { return stk_min.top(); }
};
【字符串解码】
给定一个经过编码的字符串返回它解码后的字符串。
编码规则为: k[encoded_string]表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的输入字符串中没有额外的空格且输入的方括号总是符合格式要求的。
此外你可以认为原始数据不包含数字所有的数字只表示重复的次数 k 例如不会出现像 3a 或 2[4] 的输入。
思路
我们可以把每一对括号想象成一个递归函数的调用和返回遇到左括号一个新的调用因此要把当前的“现场”保存下来然后先去进行内层函数的计算遇到右括号内层函数返回返回的时候要把之前保存的“现场”恢复继续进行外层函数的计算。我们用一个栈来模拟现场的保存和恢复。
class Solution {
public:string decodeString(string s) {stackint numStk;stackstring strStk;int num 0;string cur ;for (int i 0; i s.size(); i) {//数字if (s[i] 0 s[i] 9) {num num * 10 (s[i] - 0);}//括号else if (s[i] [) {numStk.push(num);num 0;strStk.push(cur);cur ;} else if (s[i] ]) {int n numStk.top();numStk.pop();string temp strStk.top();strStk.pop();for(int i0;in;i) {temp cur;}cur temp;}//字母else {cur s[i];}}return cur;}
};
【每日温度】
给定一个整数数组 temperatures 表示每天的温度返回一个数组 answer 其中 answer[i] 是指对于第 i 天下一个更高温度出现在几天后。如果气温在这之后都不会升高请在该位置用 0 来代替。
【柱状图最大矩形】
给定 n 个非负整数用来表示柱状图中各个柱子的高度。每个柱子彼此相邻且宽度为 1 。
求在该柱状图中能够勾勒出来的矩形的最大面积。
思路
第一题的思路就是第二题思路的一部分就放在一起讲了。
对第一题来说要找的是比自身大的因此在遍历时遇到小的先存起来只有当前元素比栈顶下标元素大时才开始弹出栈内下标直到栈内没有比当前元素更大的数时停止并把当前元素入栈。第一题做到这里就够了因为对任意元素我们只需要考虑它后面的元素而最后留在栈内的元素就是没有合法的后续元素的标0就可以。
第二题的逻辑和第一题相同只是评判条件和第一题相反因为要找的是第一个小于当前元素的找到它就找到了当前矩形的右边界而栈内元素是递增的左边界就是栈顶元素下面的元素其实不一定可能会有非严格递增的情况也就是栈顶和它下面的元素一样大但因为本题找的是最大值这样做对结果不会有影响所以就不单独拿出来讨论了。然后对最后剩余元素的处理不太一样他们延伸出的矩形一直到数组边界都是合法的所以我们把数组边界作为它的右边界来做计算左边界的选取方法不变。
class Solution
{
public:vectorint dailyTemperatures(vectorint temperatures) {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int ntemperatures.size();vectorint st(n,0);vectorint ans(n,0);int j0;for(int i0;in;i){while((j 0) temperatures[st[j]] temperatures[i]){ans[st[j]]i-st[j];j--;}j;st[j]i; }return ans;}
};
class Solution {
public:int largestRectangleArea(vectorint heights) {if (!heights.size())return 0;stackint stk;stk.push(-1);int maxArea 0;int l 0, r 0, curHeight 0, curArea 0;for (int i 0; i heights.size(); i) {//空栈或能延伸if (stk.top() -1 || heights[i] heights[stk.top()]) {stk.push(i);continue;}//把能确定面积的都算了并退栈while (stk.top() ! -1 heights[i] heights[stk.top()]) {curHeight heights[stk.top()];stk.pop();curArea (i - stk.top() - 1) * curHeight;maxArea max(maxArea, curArea);}stk.push(i);}//处理还没能出栈的//还有while (stk.top() ! -1) {curHeight heights[stk.top()];stk.pop();curArea (heights.size() - stk.top() - 1) * curHeight;maxArea max(maxArea, curArea);}return maxArea;}
};
