[20] Valid Parentheses 合法的括号
https://leetcode.com/problems/valid-parentheses
问题：给定一个字符串，判断括号匹配是否成立。
思路：
public boolean isValid(String s) {
if (s == null || s.length() == 0) return true;
Stack<Character> stack = new Stack<>();
for (Character ch : s.toCharArray()) {
if (ch == '(') {
stack.push(')');
} else if (ch == '[') {
stack.push(']');
} else if (ch == '{') {
stack.push('}');
} else {
if (stack.empty() || stack.pop() != ch) {
return false;
}
}
}
return stack.isEmpty();
}
参考讲解：
[32] Longest Valid Parentheses 最长合法的括号
https://leetcode.com/problems/longest-valid-parentheses
问题：
思路：
public int longestValidParentheses(String s) {
// 存放每一个左括号的位置
Stack<Integer> stack = new Stack<>();
int res = 0;
// 当前括号组合的最左侧边界
int start = -1;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
stack.push(i);
} else {
// 当前括号组合为空
if (stack.empty()) {
start = i;
} else {
stack.pop();
if (stack.empty()) {
res = Math.max(res, i - start);
} else {
res = Math.max(res, i - stack.peek());
}
}
}
}
return res;
}
参考讲解：
[232] Implement Queue using Stacks
https://leetcode.com/problems/implement-queue-using-stacks
问题：
思路：
private Stack<Integer> stack1 = new Stack<>();
private Stack<Integer> stack2 = new Stack<>();
/**
* 队列的 push() 操作，就直接在 stack1 上进行栈的 push() 操作即可
*/
public void push(int x) {
stack1.push(x);
}
/**
* 队列的 pop() 操作，其实就是得到 stack1 中最底下的那个元素，怎么得到呢？先把上面逐个退出的元素一个个放在另一个栈 stack2 中；
* 当 stack1 为空的时候，stack2 的栈顶元素，就是要取得的元素，用栈的 pop() 操作取出
* 在将该元素进行返回前，再将 stack2 中的元素倒回到 stack1 中，然后将该元素返回
*/
public int pop() {
// 如果stack2为空
if (stack2.isEmpty()) {
// 且stack1不为空
while (!stack1.isEmpty()) {
// 则不断把stack1中的元素pop出来，并push到stack2中暂存
stack2.push(stack1.pop());
}
}
// stack2的栈顶元素其实就是stack1的栈底元素，我们要pop队列的队首元素其实也就是pop栈的栈底元素
return stack2.pop();
}
public int peek() {
if (stack2.isEmpty()) {
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
}
return stack2.peek();
}
public boolean empty() {
return stack1.isEmpty() && stack2.isEmpty();
}
参考讲解：
[225] Implement Stack using Queues
https://leetcode.com/problems/implement-stack-using-queues
问题：
思路：
private Queue<Integer> queue = new LinkedList<>();
public void push(int x) {
queue.offer(x);
for (int i = 1; i < queue.size(); i++) {
queue.add(queue.poll());
}
}
public int pop() {
return queue.poll();
}
public int top() {
return queue.peek();
}
public boolean empty() {
return queue.isEmpty();
}
参考讲解：
[155] Min Stack
https://leetcode.com/problems/min-stack
问题：设计一个能返回栈中最小值的栈结构。
思路：考虑使用另一个辅助栈，用来存储[0..i]的最小值。
private LinkedList<Integer> list; // 存储压入栈中的所有值
private LinkedList<Integer> mins; // 存储当前栈中的最小值
public MinStack() {
list = new LinkedList<Integer>();
mins = new LinkedList<Integer>();
}
public void push(int x) {
// 如果最小值栈中没有值，或者当前元素x比最小值栈中的最小值还要小，则把x放入最小值栈中
if (mins.size() < 1 || mins.getLast() >= x) {
mins.add(x);
}
list.add(x);
}
public void pop() {
// pop 的时候，有可能 pop 出的是当前栈中的最小值。因此在 pop 函数操作时，需同时操作维护最小值的 linkedlist
if (list.getLast().equals(mins.getLast())) {
mins.removeLast();
}
list.removeLast();
}
public int top() {
return list.getLast();
}
public int getMin() {
return mins.getLast();
}
Follow Up:
Q：如果还要加一个getMax()方法呢？
A：同样用一个栈，但是入栈的判断条件是大于等于栈顶。
参考讲解：
[150] Evaluate Reverse Polish Notation
https://leetcode.com/problems/evaluate-reverse-polish-notation
问题：逆波兰表达式求值。
思路：只需要定义一个stack，如果是+, -, *, /四个运算符，就取出栈顶的两个数，进行相应操作，之后将计算得到的结果压入栈中；如果是数字，就直接入栈。最终stack只剩下一个元素，这个元素就是逆波兰表达式的值。
例如给定：["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6
- 遇到4：
stack : 4
- 遇到13：
stack : 4 13
- 遇到5：
stack : 4 13 5
- 遇到/号：
pop : b=5, a=13 -> stack : 4 -> 13/5=2, push 2 to stack -> stack : 4 2
- 遇到+号：
pop : b=2, a=4 -> stack : null -> 4+2=6, push 6 to stack -> stack : 6
- pop剩下的一个元素6，得到计算结果为6
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
for (String s : tokens) {
if (s.equals("+")) {
stack.push(stack.pop() + stack.pop());
} else if (s.equals("-")) {
int b = stack.pop();
int a = stack.pop();
stack.push(a - b);
} else if (s.equals("*")) {
stack.push(stack.pop() * stack.pop());
} else if (s.equals("/")) {
int b = stack.pop();
int a = stack.pop();
stack.push(a / b);
} else {
stack.push(Integer.parseInt(s));
}
}
return stack.pop();
}
参考讲解：
[224] Basic Calculator
https://leetcode.com/problems/basic-calculator
问题：
思路：题目中只有+ - ( )。遍历字符串，对于每个字符c：
- 如果是数字，则一直遍历到非数字字符，把数字找出，并与结果相加
- 如果是
+``-符号，将符号位sign设置成对应的值
- 如果是
(，将res和sign压入栈中，重置res和sign
- 如果是
)，将sign和res弹出栈，并计算结果
例如给定：1 + 3 - (2 - 3)
- 遇到1：
sign=1 -> res=0+1*1=1
- 遇到+：
sign=1
- 遇到3：
sign=1 -> res=1+3*1=4
- 遇到-：
sign=-1
- 遇到(：
push res(4), push sign(-1), res=0, sign=1 -> stack : 4 -1
- 遇到2：
sign=1 -> res=0+2*1=2
- 遇到-：2-3相当于2+(-3) ->
sign=-1
- 遇到3：
sign=-1 -> res=2+3*(-1)=-1
- 遇到)：
res=-1*stack.pop()+stack.pop()=-1*(-1)+4=5
public int calculate(String s) {
Stack<Integer> stack = new Stack<>();
int sign = 1;
int res = 0;
for (int i = 0; i < s.length(); i++) {
if (Character.isDigit(s.charAt(i))) {
int num = s.charAt(i) - '0';
// 如果下一个还是数字，就继续计算
while (i + 1 < s.length() && Character.isDigit(s.charAt(i + 1))) {
int next = s.charAt(i + 1) - '0';
num = num * 10 + next;
i++;
}
res += num * sign;
} else if (s.charAt(i) == '+') {
sign = 1;
} else if (s.charAt(i) == '-') {
sign = -1;
} else if (s.charAt(i) == '(') {
stack.push(res);
stack.push(sign);
res = 0;
sign = 1;
} else if (s.charAt(i) == ')') {
res = res * stack.pop() + stack.pop();
}
}
return res;
}
参考讲解：
[71] Simplify Path
https://leetcode.com/problems/simplify-path
问题：解析linux路径，有”.”表示不变和”..”表示回上层。
思路：
public String simplifyPath(String path) {
Stack<String> stack = new Stack<>();
String[] paths = path.split("/+");
for (String s : paths) {
if (s.equals("..")) {
if (!stack.isEmpty()) {
stack.pop();
}
} else if (!s.equals(".") && !s.equals("")) {
stack.push(s);
}
}
String res = "";
while (!stack.isEmpty()) {
res = "/" + stack.pop() + res;
}
if (res.length() == 0) return "/";
return res;
}
参考讲解：
[84] Largest Rectangle in Histogram
https://leetcode.com/problems/largest-rectangle-in-histogram
问题：
思路：
参考讲解：
[16] Remove Duplicate Letters
https://leetcode.com/problems/remove-duplicate-letters
问题：
思路：如果一个字母c，小于前面的某个字母b，并且b在a后面还有，那么b应当被删除。
用栈来实现。
- 遍历一遍统计每个字母出现次数。
- 再遍历一遍，对当前字母c的统计数字减一。
- 如果c不在栈中，则进行如下栈操作：
- 如果当前字母c小于栈顶，并且栈顶元素还有剩余，则出栈栈顶，并标记栈顶不在栈中。重复该操作直到栈顶元素不满足要求或者栈为空。
- 入栈字母c，并标记c已经在栈中。
public String removeDuplicateLetters(String s) {
int[] cnt = new int[26];
boolean[] inStack = new boolean[26];
char[] st = new char[s.length()];
int len = 0;
for (char c : s.toCharArray()) {
cnt[c - 'a']++;
}
for (char c : s.toCharArray()) {
cnt[c - 'a']--;
if (!inStack[c - 'a']) {
while (len > 0 && c < st[len - 1] && cnt[st[len - 1] - 'a'] > 0) {
inStack[st[--len] - 'a'] = false;
}
st[len++] = c;
inStack[c - 'a'] = true;
}
}
return new String(st, 0, len);
}
public String removeDuplicateLetters(String s) {
if (s == null || s.length() == 0) return s;
Map<Character, Integer> map = new HashMap<>();
for (int i = 0; i < s.length(); i++) map.put(s.charAt(i), i);
char[] res = new char[map.size()];
int start = 0;
int end = findMinLastPos(map);
for (int i = 0; i < res.length; i++) {
char minChar = 'z' + 1;
for (int k = start; k <= end; k++) {
if (map.containsKey(s.charAt(k)) && s.charAt(k) < minChar) {
minChar = s.charAt(k);
start = k + 1;
}
}
res[i] = minChar;
map.remove(minChar);
if (s.charAt(end) == minChar) {
end = findMinLastPos(map);
}
}
return new String(res);
}
private int findMinLastPos(Map<Character, Integer> map) {
int res = Integer.MAX_VALUE;
for (int num : map.values()) {
res = Math.min(res, num);
}
return res;
}
参考讲解：
[《剑指offer》面试题22] 栈的压入、弹出序列
https://www.nowcoder.com/questionTerminal/d77d11405cc7470d82554cb392585106
问题：已知压栈序列，判断合法的弹出序列。输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4，5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。
思路：借用一个辅助的栈，遍历压栈顺序，先讲第一个放入栈中，这里是1，然后判断栈顶元素是不是出栈顺序的第一个元素，这里是4，很显然1≠4，所以我们继续压栈，直到相等以后开始出栈，出栈一个元素，则将出栈顺序向后移动一位，直到不相等，这样循环等压栈顺序遍历完成，如果辅助栈还不为空，说明弹出序列不是该栈的弹出顺序。
举例：入栈序列1,2,3,4,5，出栈序列4,5,3,2,1
- 首先1入辅助栈，此时栈顶1≠4，继续入栈2
- 此时栈顶2≠4，继续入栈3
- 此时栈顶3≠4，继续入栈4
- 此时栈顶4＝4，出栈4，弹出序列向后一位，此时为5，,辅助栈里面是1,2,3
- 此时栈顶3≠5，继续入栈5
- 此时栈顶5=5，出栈5,弹出序列向后一位，此时为3，,辅助栈里面是1,2,3
- ...依次执行，最后辅助栈为空。如果不为空说明弹出序列不是该栈的弹出顺序。
public boolean isPopOrder(int[] pushA, int[] popA) {
if (pushA.length == 0) return false;
Stack<Integer> stack = new Stack<>();
// 用于标识弹出序列的位置
int popIndex = 0;
for (int i = 0; i < pushA.length; ) {
stack.push(pushA[i++]);
// 如果栈不为空，且栈顶元素等于弹出序列
while (popIndex < popA.length && stack.peek() == popA[popIndex]) {
stack.pop();
// 弹出序列向后一位
popIndex++;
}
}
return stack.empty();
}
