[数据结构与算法] 栈
文章目录
栈
栈常用于后进先出的应用场景。即只能向栈顶压入元素,从栈顶弹出元素,常常使用一个单链表来实现,链头指针指向栈顶元素。 常用于在解决某个问题的时候,只要求关心最近一次的操作,并且在操作完成了之后,需要向前查找到更前一次的操作。另外还常用于解除递归的操作。
关键词:后入先出 ,最近操作
20 有效的括号
给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。
有效字符串需满足:左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。
示例 1:
输入: "()"
输出: true
输入: "()[]{}"
输出: true
class Solution {
public boolean isValid(String s) {
if (s == null || "".equals(s)) {
return true;
}
if (s.length() % 2 != 0) {
return false;
}
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if ('('==c || '['==(c) || '{'==c) {
stack.push(c);
} else {
if (stack.empty()){
return false;
}
if (isMatch(stack.peek(),c)) {
stack.pop();
}
}
}
return stack.size() == 0;
}
boolean isMatch(char c1, char c2) {
if (c1 == '(' && c2 == ')' || c1 == '[' && c2 == ']' || c1 == '{' && c2 == '}') {
return true;
}
return false;
}
}
739 每日温度
根据每日 气温 列表,请重新生成一个列表,对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高,请在该位置用 0 来代替。
例如,给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73],你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。
提示:气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度,都是在 [30, 100] 范围内的整数。
来源:力扣(LeetCode)
-
暴力解决
循环就完事了,需要注意的是,题目要求输出的是index,而不是结果,所以解答的时候要稍微注意下.
class Solution { public int[] dailyTemperatures(int[] T) { int[] res = new int[T.length]; for(int i =0;i < T.length;i++){ int current = T[i]; res[i]=0; for( int j = i+1;j<T.length;j++){ if(T[j]>current){ res[i] = j-i; break; }else{ continue; } } } return res; } } -
使用堆栈
从上面暴力解法的solution中, 我们留意到,我们在遍历后续元素进行了多余的遍历,例如,当index=2,current=75时,我们分别拿71,69,72与current比较,但均比current小,res[2]无法取得结果,需要继续遍历与current比较,但是在这个过程中,我们能够知道71,69的结果是72,即res[3],res[4]分别为2,1,所以在这个过程中我们进行了多余的遍历与比较,增加了时间开销,因此我们不妨将暂时获取得不到res的元素存放在堆栈中,当能得到res时,出栈,利用堆栈后进先出的特性(就近比较),这样我们仅仅需要遍历一边数组就可以得到答案,具体步骤如下:- 令res为返回的数组结结果, current=73, stack 为空,T[0]入栈(下标);
- current = 74, index = 1, T[1] = 74>73? 是, res[0] = 1-0=1, T[0] 出栈;
- stack 为空, T[1]入栈;
- current = 75, index = 2, T[2]=75>74? 是, res[1] =2-1=1, T[1]出栈;
- stack为空, T[2] 入栈;
- current = 71, index = 3, T[3] = 71>75 ? 否. T[3] 入栈;
- current = 69, index = 4, T[4] = 69>71? 否. T[4] 入栈;
- current = 72, index = 5, T[5] = 72>69? 是. res[4] = 5-4 = 1, T[4] 出栈;
- current = 72, index = 5, T[5] = 72>71? 是. res[3] = 5-3 = 2, T[3] 出栈;
- current = 72, index = 5, T[5]=72>75? 否, T[5]入栈;
- current = 76, index = 6, T[6] =76 >72? 是, res[5] = 6-5=1, T[5] 出栈;
- current = 76, index = 6, T[6] = 76 >75? 是, res[2] = 6-2 = 4,T[2] 出栈;
- stack为空, T[6] 入栈;
- current = 63, index = 7, T[7]=63>76? 否; T[7] 入栈;
- 数组到达边界,弹出栈元素res[7] =0;res[6]=0.
class Solution {
public int[] dailyTemperatures(int[] T) {
int[] res = new int[T.length];
Stack<Integer> stack = new Stack<>();
for (int i = 0; i <T.length ; i++) {
int current = T[i];
while (!stack.isEmpty()&¤t>T[stack.peek()]){
int lastIndex = stack.peek();
int last = T[lastIndex];
if (current>last){
res[lastIndex] = i- lastIndex;
stack.pop();
}
}
stack.push(i);
}
while (!stack.isEmpty()){
int index = stack.pop();
res[index] = 0;
}
return res;
}
}
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论