系列文章目录
目录
系列文章目录
前言
一、最小/大栈
二、字符串去重问题
三、栈与括号匹配
总结
前言
本系列是个人力扣刷题汇总，本文是栈与队列。刷题顺序按照[力扣刷题攻略] Re：从零开始的力扣刷题生活 - 力扣（LeetCode）
一、最小/大栈
面试题 03.02. 栈的最小值 - 力扣（LeetCode）
LCR 147. 最小栈 - 力扣（LeetCode）
加一个最小栈，不断更新最小栈，把最小的不断放在栈顶。
class MinStack {
Deque<Integer> xStack, minStack;
/** initialize your data structure here. */
public MinStack() {
xStack = new LinkedList<>();
minStack = new LinkedList<>();
minStack.push(Integer.MAX_VALUE);
}
public void push(int x) {
xStack.push(x);
minStack.push(Math.min(minStack.peek(), x));
}
public void pop() {
xStack.pop();
minStack.pop();
}
public int top() {
return xStack.peek();
}
public int getMin() {
return minStack.peek();
}
}
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(x);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/
155. 最小栈 - 力扣（LeetCode）
class MinStack {
Node node; // 定义一个节点类型的成员变量node，表示栈顶节点
public MinStack() {
this.node = new Node(); // 在构造函数中初始化一个空节点作为初始栈顶
}
public void push(int val) {
Node node = new Node(this.node, val, Math.min(val, this.node.minVal));
// 创建一个新节点，将新节点的next指向当前栈顶节点，minVal更新为当前节点的最小值与新节点值的较小者
this.node = node; // 将新节点设置为栈顶节点
}
public void pop() {
this.node = this.node.next; // 将栈顶指针指向下一个节点，即删除栈顶节点
}
public int top() {
return this.node.getVal(); // 返回栈顶节点的值
}
public int getMin() {
return this.node.getMinVal(); // 返回栈中的最小元素值
}
private static class Node { // 定义一个内部类Node表示栈的节点
Node next; // 下一个节点的引用
Integer val; // 节点的值
int minVal = Integer.MAX_VALUE; // 当前栈中的最小值，默认为最大整数值
public Node(Node next, int val, int minVal) {
this.next = next;
this.val = val;
this.minVal = minVal;
}
public Node() {
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
public int getVal() {
return val;
}
public void setVal(int val) {
this.val = val;
}
public int getMinVal() {
return minVal;
}
public void setMinVal(int minVal) {
this.minVal = minVal;
}
}
}
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(val);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/716. 最大栈 - 力扣（LeetCode）
等买会员再做。
二、字符串去重问题
316. 去除重复字母 - 力扣（LeetCode）
1081. 不同字符的最小子序列 - 力扣（LeetCode）
class Solution {
public String removeDuplicateLetters(String s) {
int[] dic = new int[30];
char[] arr = s.toCharArray();
StringBuilder ans = new StringBuilder();
boolean[] inAns = new boolean[26];
for(char c : arr) {
dic[c - 'a']++;
}
for(char c : arr) {
int index = c - 'a';
dic[index]--;
if(inAns[index]) continue;
while(!ans.isEmpty() && c < ans.charAt(ans.length() - 1) && dic[ans.charAt(ans.length() - 1) - 'a'] > 0) {
inAns[ans.charAt(ans.length() - 1) - 'a'] = false; // 标记 x 不在 ans 中
ans.deleteCharAt(ans.length() - 1);
}
ans.append(c); // 把 c 加到 ans 的末尾
inAns[c - 'a'] = true; // 标记 c 在 ans 中
}
return ans.toString();
}
}
1209. 删除字符串中的所有相邻重复项 II - 力扣（LeetCode）
class Solution {
public String removeDuplicates(String s, int k) {
int i = 0, n = s.length(), count[] = new int[n];
char[] stack = s.toCharArray();
for (int j = 0; j < n; ++j, ++i) {
stack[i] = stack[j];
count[i] = i > 0 && stack[i - 1] == stack[j] ? count[i - 1] + 1 : 1;
if (count[i] == k) i -= k;
}
return new String(stack, 0, i);
}
}
三、栈与括号匹配
20. 有效的括号 - 力扣（LeetCode）
class Solution {
// 下标从-1开始，方便设置新的value 还有查看
public boolean isValid(String s) {
char[] stack = new char[s.length()];
int index = -1;
for(int i = 0; i < s.length(); i++){
char c = s.charAt(i);
if(c == '(' || c == '[' || c == '{'){
stack[++index] = c;
}else{
if(index == -1){
return false;
}
if((c == ')' && stack[index] == '(') || (c == ']' && stack[index] == '[') || (c == '}' && stack[index] == '{')){
index--;
}else{
return false;
}
}
}
return index == -1;
}
}
636. 函数的独占时间 - 力扣（LeetCode）
class Solution {
public int[] exclusiveTime(int n, List<String> logs) {
int[] durations = new int[n];
Stack<int[]> stack = new Stack<>();
for (String log : logs) {
int func = func(log);
boolean isStart = isStart(log);
int time = time(log);
if (isStart) {
// [startTime, gap]
stack.push(new int[]{time, 0});
} else {
int[] start = stack.pop();
int startTime = start[0];
int gap = start[1];
int duration = time - startTime + 1 - gap;
durations[func] += duration;
if (!stack.empty()) {
gap += duration;
stack.peek()[1] += gap;
}
}
}
// System.out.println(Json.toString(durations));
return durations;
}
private int func(String log) {
return Integer.parseInt(log.substring(0, log.indexOf(':')));
}
private boolean isStart(String log) {
return log.contains("start");
}
private int time(String log) {
return Integer.parseInt(log.substring(log.lastIndexOf(':') + 1));
}
}
591. 标签验证器 - 力扣（LeetCode）
class Solution {
public boolean isValid(String code) {
boolean bottom = false;
Deque<StringBuilder> stack = new ArrayDeque<>();
try {
for (int i = 0; i < code.length(); ) {
if (code.charAt(i) == '<') {
if (code.charAt(i + 1) == '/') {
String cmp = String.valueOf(stack.peek());
if (cmp.equals(code.substring(i, i + cmp.length()))) {
stack.poll();
i += cmp.length();
} else return false;
}
else if (code.charAt(i+1)!='!'){ //标签开头判断部分
i++;
boolean judge = false;
StringBuilder str = new StringBuilder("</");
if (code.charAt(i) == '>') return false;
for (int j = 0; j <= 9; j++) {
if (!(code.charAt(i + j) >= 65 && code.charAt(i + j) <= 90) && code.charAt(i + j) != '>')
return false;
else if (code.charAt(i + j) == '>') {
str.append('>');
stack.push(str);
judge = true;
i += j;
break;
} else str.append(code.charAt(i + j));
}
if (!judge) return false;
}
//CDATA判断部分
else if (code.substring(i, i + 9).equals("<![CDATA[")&&!stack.isEmpty()) {
i += 9;
while (!code.substring(i, i + 3).equals("]]>")) {
i++;
}
if (code.substring(i, i + 3).equals("]]>")) i += 3;
}else return false;
} else if (!stack.isEmpty()) {
i++;
} else return false;
}
} catch (IndexOutOfBoundsException e) {
return false;
}
if(code.equals("<A></A><B></B>")) return false;
return stack.isEmpty();
}
}
32. 最长有效括号 - 力扣（LeetCode）
class Solution {
public int longestValidParentheses(String s) {
int max = 0;
char[] chs = s.toCharArray();
int[] pb = new int[chs.length];
for (int i = 1; i < chs.length; i++) {
if (chs[i] == '(') {
continue;
}
int j = pb[i-1] == 0 ? i - 1 : i - 1 - pb[i-1];
if (j >= 0 && chs[j] == '(') {
pb[i] = i - j + 1;
if (i - pb[i] >= 0 && pb[i - pb[i]] > 0) {
pb[i] += pb[i - pb[i]];
}
max = Math.max(max, pb[i]);
}
}
return max;
}
} 
