leetcode 经典栈相关题目(思路、方法、code)

发表于 | 更新于 | 分类于 | 阅读次数：
本文字数： 3.5k | 阅读时长 ≈ 3 分钟

刷几条栈相关的题目。

20. 有效的括号

给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串，判断字符串是否有效。

有效字符串需满足：

  • 左括号必须用相同类型的右括号闭合
  • 左括号必须以正确的顺序闭合
  • 注意空字符串可被认为是有效字符串
1
2
3
4
5
6
示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool isValid(string s) 
	{
    	stack<char> st;
		for(int i=0;i<s.size();i++)
		{
			if(s[i]=='('||s[i]=='{'||s[i]=='[') //左括号加入
				st.push(s[i]);
			else if(st.size()>0&&(s[i]==')'&&st.top()=='('||s[i]==']'&&st.top()=='['||s[i]=='}'&&st.top()=='{'))//右括号需要判断能否消除,不能消除即出错
				st.pop();
			else
				return false;	
		}
		if(st.size()==0)
			return true;
		return false;    
    }
};
  1. 最小栈
    设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
1
2
3
4
push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。

分析：通常的栈结构，push,pop,top均可以满足，但是 getMin()不能满足，能否增添一个变量用来标记最小值？如果有这个变量，则每次push元素我们都可以将元素进行比较，这样就可以O(1)获取最小元素。但是仔细想想，如果将最小元素pop了出来，那么现在的最下元素怎样标记？只能遍历获得，因此最终是O(n)获取最小元素。

故需要转换思路，怎样才能动态地存取最小元素？采用辅助栈。

使用两个栈，一个栈作为正常栈，另一个栈作为辅助栈。辅助栈用来存取当前的最小值，如果最小值更新，则压入新的最小值即可。

使用两个栈，一个栈作为正常栈，另一个栈作为辅助栈。辅助栈用来存取当前的最小值，如果最小值更新，则压入新的最小值即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
入栈 3 
|   |    |   |
|   |    |   |
|_3_|    |_3_|
stack  minStack

入栈 5 ,5大于minStack的栈顶，故不压入
|   |    |   |
| 5 |    |   |
|_3_|    |_3_|
stack  minStack

入栈 2 ，2小于最小值栈的栈顶，故将其入栈
| 2 |    |   |
| 5 |    | 2 |
|_3_|    |_3_|
stack  minStack

出栈 2，发现2是最小栈的栈顶，故minStack也出栈
|   |    |   |
| 5 |    |   |
|_3_|    |_3_|
stack  minStack

出栈 5，发现5不是最小栈的栈顶，因此minStack 不处理
|   |    |   |
|   |    |   |
|_3_|    |_3_|
stack  minStack
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class MinStack {
	private:
		stack<int> data;
		stack<int> min;
public:
    /** initialize your data structure here. */
    MinStack() 
	{
        
    }
    
    void push(int x) 
	{
        data.push(x);
		if(!min.empty()&&x<=min.top()) //最小栈不是空且最小栈栈顶元素小于等于x，则入栈 
			min.push(x); 
		if(min.empty()) //最小栈为空 
        	min.push(x);
    }
    void pop() 
	{
		if(data.top()==min.top()) //如果要pop的元素等于最小栈栈顶，则将其pop 
			min.pop();
		data.pop();   
    }
    
    int top() 
	{
      return data.top();  //返回data的栈顶即可  
    }
    
    int getMin() 
	{
        return min.top(); //返回min的栈顶即可 
    }
};

946. 验证栈序列

给定 pushed 和 popped 两个序列，每个序列中的 值都不重复，只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时，返回 true；否则，返回 false。

1
2
3
4
5
6
7
8
9
10
11
示例 1：
输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出：true
解释：我们可以按以下顺序执行：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

示例 2：
输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
输出：false
解释：1 不能在 2 之前弹出。

用栈来模拟这个过程即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) 
    {
		stack<int> S;
		int length=pushed.size();
		int j=0;
		for(int i=0;i<length;i++)
		{
			S.push(pushed[i]);
			while(!S.empty()&&S.top()==popped[j]) //每次push后都要将能消除的消除了	
			{
				S.pop();
				j++;
			}
		}
		if(!S.empty())
			return false;
		return true; 
    }
};
  1. 下一个更大元素 I
    给定两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2中的下一个比其大的值。

nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 −1。

1
2
3
4
5
6
7
示例 1:
输入: nums1 = [4,1,2], nums2 = [1,3,4,2].
输出: [-1,3,-1]
解释:
    对于num1中的数字4，你无法在第二个数组中找到下一个更大的数字，因此输出 -1。
    对于num1中的数字1，第二个数组中数字1右边的下一个较大数字是 3。
    对于num1中的数字2，第二个数组中没有下一个更大的数字，因此输出 -1。

此处忽略先。

84. 柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

1
2
3
输入: [2,1,5,6,2,3]
输出: 10
自己画图看看。

困难，以后再做。

-------------本文结束有空来玩-------------
坚持原创技术分享，您的支持将鼓励我继续创作！