队列实现栈:https://leetcode-cn.com/problems/implement-stack-using-queues/
class MyStack { Queue<Integer> queue = new LinkedList<>(); public MyStack() { } public void push(int x) { queue.add(x); } public int pop() { //头尾倒置 for(int i=0;i<queue.size()-1;i++){ queue.add(queue.poll()); } return queue.poll(); } public int top() { //头尾倒置 for(int i=0;i<queue.size()-1;i++){ queue.add(queue.poll()); } int result = queue.poll(); queue.add(result); return result; } public boolean empty() { return queue.isEmpty(); } }
栈实现队列:https://leetcode-cn.com/problems/implement-queue-using-stacks/
class MyQueue { Stack<Integer> stack1 = new Stack<>(); Stack<Integer> stack2 = new Stack<>(); public MyQueue() { } public void push(int x) { stack1.push(x); } public int pop() { if(stack2.isEmpty()){ while(!stack1.isEmpty()){ stack2.push(stack1.pop()); } } if(stack2.isEmpty()){ return -1; }else{ return stack2.pop(); } } public int peek() { if(stack2.isEmpty()){ while(!stack1.isEmpty()){ stack2.push(stack1.pop()); } } if(stack2.isEmpty()){ return -1; }else{ return stack2.peek(); } } public boolean empty() { return stack1.isEmpty() && stack2.isEmpty(); } }
最小栈:https://leetcode-cn.com/problems/min-stack/
class MinStack { Stack<Integer> stack = new Stack<>(); Stack<Integer> min = new Stack<>(); public MinStack() { } public void push(int x) { stack.push(x); //min栈顶维护最小值 if(min.isEmpty() || min.peek() >= x){ min.push(x); } } public void pop() { if(stack.pop().equals(min.peek())){ min.pop(); } } public int top() { return stack.peek(); } public int getMin() { return min.peek(); } }
队列的最大值:https://leetcode-cn.com/problems/dui-lie-de-zui-da-zhi-lcof/
class MaxQueue { LinkedList<Integer> queue = new LinkedList<>(); LinkedList<Integer> max = new LinkedList<>(); public MaxQueue() { } public int max_value() { if(queue.isEmpty()){ return -1; }else{ return max.peekFirst(); } } public void push_back(int value) { queue.addLast(value); //max队列的队尾维护最大值,先弹出再存入 while(!max.isEmpty() && max.peekLast() <= value){ max.pollLast(); } max.addLast(value); } public int pop_front() { if(queue.isEmpty()){ return -1; } int result = queue.pollFirst(); if(max.peekFirst().equals(result)){ max.pollFirst(); } return result; } }
- 有效括号:https://leetcode-cn.com/problems/valid-parentheses/
class Solution { public boolean isValid(String s) { //单调栈,栈存入右半,如果栈为空或者栈顶不等于下一个字符,则无法闭合,返回false Stack<Character> stack = new Stack<>(); char[] str = s.toCharArray(); for(char c : str){ if(c == '('){ stack.push(')'); }else if(c == '['){ stack.push(']'); }else if(c == '{'){ stack.push('}'); }else if(stack.isEmpty() || stack.pop() != c){ return false; } } //返回栈是否为空 return stack.isEmpty(); } }
最长有效括号:https://leetcode-cn.com/problems/longest-valid-parentheses/
class Solution { public int longestValidParentheses(String s) { Stack<Integer> stack = new Stack<>(); //预存-1,用于匹配第一个字符为右半括号的情况 stack.push(-1); char[] str = s.toCharArray(); int result = 0; for(int i=0;i<str.length;i++){ if(str[i] == '('){ stack.push(i); }else{ //匹配,弹出栈顶 stack.pop(); //如果栈顶弹出后栈为空,从当前位置重新统计,否则计算长度 if(stack.isEmpty()){ stack.push(i); }else{ result = Math.max(result,i-stack.peek()); } } } return result; } }
柱状图中最大矩形:https://leetcode-cn.com/problems/largest-rectangle-in-histogram/
class Solution { public int largestRectangleArea(int[] heights) { //复制一个数组,在头尾插入高度为0的柱体 int[] temp = new int[heights.length+2]; System.arraycopy(heights,0,temp,1,heights.length); Stack<Integer> stack = new Stack<>(); int result = 0; for(int i=0;i<temp.length;i++){ //找到第一个比栈顶小的元素 while(!stack.isEmpty() && temp[stack.peek()] > temp[i]){ //提取栈顶为高 int high = temp[stack.pop()]; int width = i - stack.peek()-1; result = Math.max(result,high*width); } stack.push(i); } return result; } }
每日温度:https://leetcode-cn.com/problems/daily-temperatures/
class Solution { public int[] dailyTemperatures(int[] T) { Stack<Integer> stack = new Stack<>(); int[] result = new int[T.length]; for(int i=0;i<T.length;i++){ //当前元素比栈顶大时,提取栈顶作为索引,计算天数差值 while(!stack.isEmpty() && T[stack.peek()] < T[i]){ int index = stack.pop(); result[index] = i - index; } stack.push(i); } return result; } }
滑动窗口最大值:https://leetcode-cn.com/problems/sliding-window-maximum/
class Solution { public int[] maxSlidingWindow(int[] nums, int k) { LinkedList<Integer> queue = new LinkedList<>(); //窗口数组 int[] result = new int[nums.length - k + 1]; int index = 0; for(int i=0;i<nums.length;i++){ while(!queue.isEmpty() && nums[queue.peekLast()] < nums[i]){ queue.pollLast(); } queue.addLast(i); //如果左边界i-k == queue.peekFirst(),说明要右移,弹出队首 if(i-k == queue.peekFirst()){ queue.pollFirst(); } //如果右边界i >= k-1,要存入 if(i >= k-1){ result[index++] = nums[queue.peekFirst()]; } } return result; } }