栈、单调栈、队列、单调队列
Java中栈的使用
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
| import java.util.Stack;
public class StackExample {
public static void main(String[] args) {
Stack<Integer> stack = new Stack<>();
stack.push(10);
stack.push(20);
stack.push(30);
int topElement = stack.pop();
System.out.println("出栈元素：" + topElement);
int peekElement = stack.peek();
System.out.println("栈顶元素：" + peekElement);
boolean isEmpty = stack.isEmpty();
System.out.println("栈是否为空：" + isEmpty);
int size = stack.size();
System.out.println("栈的大小：" + size);
}
}
|
入栈push、出栈pop、栈顶peek、判空isEmpty、大小size
栈
括号匹配
https://leetcode.cn/problems/valid-parentheses/
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
| class Solution {
public boolean isValid(String s) {
Stack<Character> stk = new Stack<>();
for(char ch: s.toCharArray()){
if(ch == '(' || ch=='[' || ch=='{'){
stk.push(ch);
}
else if (ch ==')'){
if(!stk.isEmpty() && stk.peek() == '(')
stk.pop();
else return false;
}
else if (ch =='}'){
if(!stk.isEmpty() && stk.peek() == '{')
stk.pop();
else return false;
}
else if (ch ==']'){
if(!stk.isEmpty() && stk.peek() == '[')
stk.pop();
else return false;
}
}
return stk.isEmpty() ? true:false;
}
}
|
比较含退格的字符串
https://leetcode.cn/problems/backspace-string-compare/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public String handle(String s){
Stack<Character> stk = new Stack<>();
for(char ch: s.toCharArray()){
if(ch =='#'){
if(!stk.isEmpty()) stk.pop();
}else
stk.push(ch);
}
StringBuilder sb = new StringBuilder();
while(!stk.isEmpty())
sb.append(stk.pop());
return sb.toString();
}
public boolean backspaceCompare(String s, String t) {
String hs = handle(s);
String ht = handle(t);
return hs.equals(ht) ? true:false;
}
}
|
字符串去重
https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public String removeDuplicates(String s) {
Stack<Character> stk = new Stack<>();
for(char ch: s.toCharArray()){
if(!stk.isEmpty() && stk.peek()==ch){
stk.pop();
}
else
stk.push(ch);
}
StringBuilder sb = new StringBuilder();
while(!stk.isEmpty()){
sb.append(stk.pop());
}
return sb.reverse().toString();
}
|
逆波兰式求值
https://leetcode.cn/problems/evaluate-reverse-polish-notation/description/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stk = new Stack<>();
for(int i=0; i<tokens.length; ++i){
String token = tokens[i];
if(token.equals("+") || token.equals("-") || token.equals("*") || token.equals("/") ){
int m = stk.pop();
int n = stk.pop();
if(token.equals("+")) stk.push(n+m);
if(token.equals("-")) stk.push(n-m);
if(token.equals("*")) stk.push(n*m);
if(token.equals("/")) stk.push(n/m);
}
else{
stk.push(Integer.valueOf(token));
}
}
return stk.pop();
}
}
|
遇数字入栈，遇符号出栈。逆波兰式本身就是后序遍历。
栈实现队列
https://leetcode.cn/problems/implement-queue-using-stacks/
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
| class MyQueue {
private Stack<Integer> stkIn;
private Stack<Integer> stkOut;
public MyQueue() {
stkIn = new Stack<>();
stkOut = new Stack<>();
}
public void push(int x) {
stkIn.push(x);
}
public int pop() {
if(stkOut.isEmpty()){
while(!stkIn.isEmpty()) stkOut.push(stkIn.pop());
}
return stkOut.pop();
}
public int peek() {
if(stkOut.isEmpty()){
while(!stkIn.isEmpty()) stkOut.push(stkIn.pop());
}
return stkOut.peek();
}
public boolean empty() {
return stkIn.isEmpty() && stkOut.isEmpty();
}
}
|
两个栈，一个栈用于填入元素，另一个栈用于弹出元素。当要弹出元素时，将第一个栈的元素倒入第二个栈中，自然形成了先进先出的顺序。
字符串解码
https://leetcode.cn/problems/decode-string/
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
| class Solution {
public String decodeString(String s) {
StringBuilder res = new StringBuilder();
int num=0;
Stack<Integer> num_stk = new Stack<>();
Stack<String> ch_stk = new Stack<>();
for(char ch : s.toCharArray()){
if('0'<=ch && ch<='9'){
num = 10*num + ch-'0';
}else if(ch == '['){
num_stk.push(num);
ch_stk.push(res.toString());
num = 0;
res = new StringBuilder();
}else if(ch == ']'){
StringBuilder tmp = new StringBuilder();
int cnt = num_stk.pop();
for(int i=0; i<cnt; ++i) tmp.append(res);
res = new StringBuilder(ch_stk.pop() + tmp.toString());
}else{
res.append(ch);
}
}
return res.toString();
}
}
|
这题难点在于处理多位数字以及处理解码的语义。
在实现中，借助两个栈，数字栈和字符栈；同时利用一个局部变量存储当前解码内容。
比如“8[7[a6[bc]]]“，数字栈的使用也是因为会出现数字嵌套的情形。
单调栈
原理
单调栈就是维护一个单调递增或递减的栈。
那么，它有什么用？求下一个更大的数，就要想到单调栈。
在使用单调栈的时候首先要明确如下两点：
单调栈里存放的元素是什么？是元素的下标还是元素本身。
单调栈里元素是递增呢？ 还是递减呢？
每日温度
https://leetcode.cn/problems/daily-temperatures/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public int[] dailyTemperatures(int[] tem) {
Stack<Integer> stk = new Stack<>();
int[] ans = new int[tem.length];
stk.push(0);
for(int i=1; i<tem.length; ++i){
while(!stk.isEmpty() && tem[i]> tem[stk.peek()]){
int k = stk.pop();
ans[k] = i-k;
}
stk.push(i);
}
return ans;
}
|
暴力做法是直接对每个元素后面的元素进行扫描，找到第一个更大的元素为止。这种做法时间复杂度是N^ 2，因为它没有考虑到每次扫描留下的信息。一次扫描后，我们就知道了整个数组的信息，但暴力法在求后一个元素的更大元素时，还是装作什么都不知道，重新再往后扫描一遍。
有什么办法能留住扫描的信息？有，用一个栈来记录我们遍历过的元素，维持单调递减的顺序。从另外一个角度出发，当前元素是哪一个元素的“下一个更大的元素”？
采用单调栈的算法，遍历到第k个元素时，更新的是k之前的元素的答案。当栈里的元素被弹出时，它就遇到了下一个更大的元素。
下一个更大元素
https://leetcode.cn/problems/next-greater-element-i/
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
| class Solution {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
Map<Integer, Integer> map = new HashMap<>();
for(int i=0; i<nums2.length; ++i){
map.put(nums2[i], i);
}
int[] ans = new int[nums2.length];
Arrays.fill(ans, -1);
Stack<Integer> stk = new Stack<>();
for(int i=nums2.length-1; i>=0; --i){
while(!stk.isEmpty() && stk.peek()<=nums2[i]){
stk.pop();
}
ans[i] = stk.isEmpty()?-1:stk.peek();
stk.push(nums2[i]);
}
for(int i=0; i<nums1.length; ++i){
int num = nums1[i];
int value = map.get(num);
nums1[i] = ans[value];
}
return nums1;
}
}
|
下一个更大的元素2
https://leetcode.cn/problems/next-greater-element-ii/description/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public int[] nextGreaterElements(int[] nums) {
int n = nums.length;
int[] ret = new int[n];
Arrays.fill(ret, -1);
Deque<Integer> stack = new LinkedList<Integer>();
for (int i = 0; i < n * 2 - 1; i++) {
while (!stack.isEmpty() && nums[stack.peek()] < nums[i % n]) {
ret[stack.pop()] = nums[i % n];
}
stack.push(i % n);
}
return ret;
}
}
|
题目大意：循环数组的下一个更大元素。
朴素的想法，将数组扩大一倍，然后应用单调栈算法实现。在更新答案时，下标映射回原来下标。
但是不必实际扩大数组，采用取模运算。
接雨水
https://leetcode.cn/problems/trapping-rain-water/
（1）暴力思路
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public int trap(int[] height) {
int N = height.length;
int[] left = new int[N];
int[] right = new int[N];
left[0] = height[0];
right[N-1] = height[N-1];
for(int i=1; i<N; ++i){
left[i] = Math.max(height[i], left[i-1]);
right[N-1-i] = Math.max(height[N-1-i], right[N-i]);
}
int res = 0;
for(int i=1; i<N-1; ++i){
int locHeight = Math.min(left[i-1], right[i+1]);
if( height[i] > locHeight)
continue;
else
res += (locHeight - height[i]);
}
return res;
}
}
|
接雨水的本质是什么？这道题是一个数组的有条件计算，计算数组的两个大数之间凹陷的面积。最简单的思路：找出所有凹陷的面积，然后相加。
问题拆解：
不能指望一个公式计算出凹陷的面积。拆分来看，要么横着算，要么竖着计算。
显然竖着计算比较简单。第k个位置，如果两边有比它大的数，说明它处在一个凹陷处，雨水的高度取决于两边最高的墙的最低那个。在计算雨水高度时，还可以利用动态规划加速。
由于每次都要遍历计算一个数两边比它大的数，可以考虑用数组存起来。
- left[i] 计算从0到i最大的数
- right[i]计算从i到n最大的数
总体时间复杂度O（N）。
（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 int trap(int[] height) {
Stack<Integer> stk = new Stack<>();
int ans = 0;
stk.push(0);
for(int i=1; i< height.length; ++i){
while(!stk.isEmpty() && height[i]>=height[stk.peek()]){
int mid = height[stk.peek()];
stk.pop();
if(!stk.isEmpty() ){
int w = i - stk.peek() -1;
int h = Math.min(height[i],height[stk.peek()])-mid;
ans += w*h;
}
}
stk.push(i);
}
return ans;
}
}
|
水平计算，矩形水体的长度就是下一个更大的数。怎么理解？当前第k个位置是开始，那么长度就是nextGreate（k）-k。
那么高度怎么计算？高度就是Math.min(height[i],height[stk.peek()])-mid; 相当于两边最高的最低。
柱状图最大矩形
https://leetcode.cn/problems/largest-rectangle-in-histogram/
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
37
38
39
40
41
42
| class Solution {
public int largestRectangleArea(int[] h) {
int[] rLow = new int[h.length];
int[] lLow = new int[h.length];
Stack<Integer> stk = new Stack<>();
for(int i=0; i<h.length;++i){
while(!stk.isEmpty() && h[i]<h[stk.peek()]){
int val = stk.pop();
rLow[val] = i-val;
}
stk.push(i);
}
while(!stk.isEmpty()){
int val = stk.pop();
rLow[val] = h.length-val;
}
for(int i=h.length-1; i>=0; i--){
while(!stk.isEmpty() && h[i]<h[stk.peek()]){
int val = stk.pop();
lLow[val] = val-i;
}
stk.push(i);
}
while(!stk.isEmpty()){
int val = stk.pop();
lLow[val] = val+1;
}
int ans = Integer.MIN_VALUE;
for(int i=0; i<h.length; ++i){
ans = Math.max(ans, (rLow[i]+lLow[i]-1)*h[i]);
}
return ans;
}
}
|
这题其实与接雨水类似，垂直计算每一个尽可能大的矩形面积。固定矩形的高度为当前元素的值，那么要获取大面积的矩形，则将宽度向两边延伸，自然求下一个更小的数。
队列
队列实现栈
https://leetcode.cn/problems/implement-stack-using-queues/
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
| class MyStack {
private Queue<Integer> que1;
private Queue<Integer> que2;
public MyStack() {
que1 = new LinkedList<>();
que2 = new LinkedList<>();
}
public void push(int x) {
while(!que1.isEmpty()){
que2.add(que1.remove());
}
que1.add(x);
while(!que2.isEmpty()){
que1.add(que2.remove());
}
}
public int pop() {
return que1.remove();
}
public int top() {
return que1.peek();
}
public boolean empty() {
return que1.isEmpty();
}
}
|
用队列模拟栈，用到了两个队列。这里的思路是：让元素在一个队列内保持栈的排列。利用辅助队列使得第一个队列的队头成为栈头。
单调队列
原理
维护元素单调递减或单调递增的队列就是单调队列。
主要应用场景： 求滑动窗口的最大最小值。
主要思想：队列没有必要维护窗口里的所有元素，只需要维护有可能成为窗口里最大值的元素就可以了，同时保证队列里的元素数值是由大到小的。
代码：
- 入队时，将元素与队尾元素比较，直到适合它的位置（保持单调）。
- 出队时，将滑动窗口最左侧的元素和单调队列队首元素比较，如果是同一个元素就直接出队，否则不用操作。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class MyQueue {
Deque<Integer> deque = new LinkedList<>();
void offer(int val) {
while (!deque.isEmpty() && val > deque.peekLast()) {
deque.pollLast();
}
deque.offer(val);
}
void poll(int val) {
if (!deque.isEmpty() && val == deque.peekFirst()) {
deque.pollFirst();
}
}
int peek() {
return deque.peekFirst();
}
}
|
滑动窗口求最大值
https://leetcode.cn/problems/sliding-window-maximum/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution{
public int[] maxSlidingWindow(int[] nums, int k) {
MyQueue myQueue = new MyQueue();
int[] ans = new int[nums.length-k+1];
for(int i=0; i<k; ++i){
myQueue.offer(nums[i]);
}
ans[0] = myQueue.peek();
for(int i=k; i<nums.length; ++i){
myQueue.poll(nums[i-k]);
myQueue.offer(nums[i]);
ans[i-k+1] = myQueue.peek();
}
return ans;
}
}
|
优先队列（堆）
原理
优先队列就是在内部维护一个堆。
堆的典型应用：topK问题，一群数据中求最大的K个数。
Java堆API使用
1
2
3
4
|
PriorityQueue<int[]> myQueue = new PriorityQueue<>(
(o1, o2) -> {return o1[1]-o2[1];}
);
|
前k个高频元素
https://leetcode.cn/problems/top-k-frequent-elements/
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
| class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
for(int num: nums){
map.put(num, 1+map.getOrDefault(num, 0));
}
PriorityQueue<int[]> myQueue = new PriorityQueue<>(
(o1, o2) -> {return o1[1]-o2[1];}
);
for(Map.Entry<Integer, Integer> entry: map.entrySet()){
if(myQueue.size()<k)
myQueue.offer(new int[]{entry.getKey(), entry.getValue()});
else{
if(entry.getValue() > myQueue.peek()[1]){
myQueue.poll();
myQueue.offer(new int[]{entry.getKey(), entry.getValue()});
}
}
}
int[] ans = new int[k];
for(int i=0; i<k; ++i)
ans[i] = myQueue.poll()[0];
return ans;
}
}
|
数据流中位数
https://leetcode.cn/problems/find-median-from-data-stream/description
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
| class MedianFinder {
private PriorityQueue<Integer> L;
private PriorityQueue<Integer> S;
public MedianFinder() {
L = new PriorityQueue<>(Collections.reverseOrder());
S = new PriorityQueue<>();
}
public void addNum(int num) {
if(L.size() == S.size()){
S.add(num);
L.add(S.poll());
}else{
L.add(num);
S.add(L.poll());
}
}
public double findMedian() {
if(L.size()>S.size()){
return L.peek();
}
return (L.peek()+S.peek())/2.0;
}
}
|
注意两个堆构成了一个数组，将数组升序排序，[L S] ，L复杂前半部分，S负责后半部分。
为了取中位数，维护大小 S <= L <= S+1，即L总是大于等于S。
添加数据时，根据L和S的大小情况，选取从S到L，还是从L到S。为什么都需要经过两次堆？因为我们不知道新加的数到底是属于哪个堆。