栈相关题目
文章目录
- 栈相关题目
- 一、[20. 有效的括号](https://leetcode-cn.com/problems/valid-parentheses/)
- 二、[155. 最小栈](https://leetcode-cn.com/problems/min-stack/)
- 三、[84. 柱状图中最大的矩形](https://leetcode-cn.com/problems/largest-rectangle-in-histogram/) , 经常回过来看看
- 四、[239. 滑动窗口最大值](https://leetcode-cn.com/problems/sliding-window-maximum/)
- 五、[641. 设计循环双端队列](https://leetcode-cn.com/problems/design-circular-deque/)
- 六、[42. 接雨水](https://leetcode-cn.com/problems/trapping-rain-water/)
一、20. 有效的括号
1.1 解法一： 使用Stack栈（FILO）来实现（可以使用双端队列代替）
public boolean isValid(String s) {
Deque<Character> deque = new LinkedList<>();
Map<Character, Character> map = new HashMap<>(3);
map.put(')', '(');
map.put('}', '{');
map.put(']', '[');
for (int i=0; i<s.length(); i++) {
char c = s.charAt(i);
if (!map.containsKey(c)) {
deque.addFirst(c);
}else {
if (deque.isEmpty() || deque.peek()!=map.get(c)) return false;
deque.removeFirst();
}
}
return deque.isEmpty();
}
二、155. 最小栈
2.1 解法一：自定义栈
栈：先进先出。最小栈：每个节点保留最小值；
class MinStack {
private Node first;
private int N;
private class Node {
private int val;
private int min;
private Node next;
public Node(int val, int min) {
this.val = val;
this.min = min;
}
}
public MinStack() {
}
public int size() {
return N;
}
public boolean isEmpty() {
return size()==0;
}
public void push(int val) {
if (isEmpty()) {
first = new Node(val, val);
}else {
Node oldFirst = first;
first = new Node(val, Math.min(val, first.min));
first.next = oldFirst;
}
N++;
}
public void pop() {
if (isEmpty()) return;
first = first.next;
N--;
}
public int top() {
if (isEmpty()) throw new RuntimeException("None item");
return first.val;
}
public int getMin() {
if (isEmpty()) throw new RuntimeException("None item");
return first.min;
}
}
2.2 解法二：使用辅助栈
class MinStack {
private Deque<Integer> stack;
private Deque<Integer> minStack;
public MinStack() {
stack = new LinkedList<>();
minStack = new LinkedList<>();
minStack.push(Integer.MAX_VALUE);
}
public void push(int val) {
stack.push(val);
minStack.push(Math.min(val, minStack.peek()));
}
public void pop() {
stack.pop();
minStack.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return minStack.peek();
}
}
三、84. 柱状图中最大的矩形 , 经常回过来看看
3.1 解法一：暴力求解，时间超限
public int largestRectangleArea(int[] heights) {
int max = 0;
for (int i=0; i<heights.length; i++) {
int minH = heights[i];
for (int j=i; j<heights.length; j++) {
minH = Math.min(heights[j], minH);
int area = (j-i+1) * minH;
max = Math.max(area, max);
}
}
return max;
}
3.2 解法二：暴力求解的优化，（以当前角标值作为高度）,时间超限
public int largestRectangleArea(int[] heights) {
int max = 0;
for (int k=0; k<heights.length; k++) {
// 找左边界 和右边界
int l = k-1, r = k+1;
while (l>=0 && heights[l]>=heights[k]) l--;
while (r<=heights.length-1 && heights[r]>=heights[k]) r++;
int area = (r-l-1) * heights[k];
max = Math.max(area, max);
}
return max;
}
3.3 解法三：用栈来解决
基于“以当前角标对应的值作为高，再获取到左边界、和右边界，进来计算出面积”
维护一个递增的栈（栈里面存放角标），这样左边界就确定了。
因为是递增，如果进栈元素比栈顶的元素小，那边右边界就也能确定了。
(1) 根据这个思路，自己写：
public int largestRectangleArea(int[] heights) {
Deque<Integer> deque = new LinkedList<>();
deque.addFirst(-1);
int max=0;
for (int i=0; i<=heights.length; i++) {
if (i==heights.length || (deque.peek()!=-1 && heights[deque.peek()]>heights[i])){
while ((i==heights.length && deque.peek()!=-1) || (deque.peek()!=-1 && heights[deque.peek()]>heights[i])) {
int h_i = deque.removeFirst();
while (deque.peek() != -1 && heights[deque.peek()] == heights[h_i]) h_i = deque.removeFirst();
int l_i = deque.peek();
int r_i = i;
int area = (r_i - l_i - 1) * heights[h_i];
max = Math.max(area, max);
}
}
deque.addFirst(i);
}
return max;
}
(2) 对代码进行优化
public int largestRectangleArea(int[] heights) {
Deque<Integer> deque = new LinkedList<>();
deque.addFirst(-1);
int max = 0;
for (int i=0; i<heights.length; i++) {
while (deque.peek()!=-1 && heights[deque.peek()]>heights[i]) {
int area = heights[deque.removeFirst()] * (i-deque.peek()-1);
max = Math.max(area, max);
}
deque.addFirst(i);
}
while (deque.peek()!=-1) {
int area = heights[deque.removeFirst()] * (heights.length - deque.peek()-1);
max = Math.max(area, max);
}
return max;
}
四、239. 滑动窗口最大值
4.1 解法一：维护一个递减队列
public int[] maxSlidingWindow(int[] nums, int k) {
int[] res = new int[nums.length-k+1];
Deque<Integer> deque = new LinkedList<>();
for (int i=0; i<nums.length; i++) {
while (!deque.isEmpty() && nums[deque.peekLast()]<=nums[i]) {
deque.removeLast();
}
deque.addLast(i);
int j = i-k+1;
if (deque.peekFirst()<j) {
deque.removeFirst();
}
if (j>=0) {
res[j] = nums[deque.peekFirst()];
}
}
return res;
}
五、641. 设计循环双端队列
class MyCircularDeque {
private Node first, last;
private int N;
private int capacity;
private class Node{
private int value;
private Node next,pre;
public Node(int value) {
this.value = value;
}
}
public MyCircularDeque(int k) {
this.capacity = k;
}
public boolean insertFront(int value) {
if (isFull()) return false;
Node node = new Node(value);
if (isEmpty()) {
first = node;
last = node;
}else {
Node oldFirst = first;
first = node;
first.next = oldFirst;
oldFirst.pre = first;
first.pre = last;
last.next = first;
}
N++;
return true;
}
public boolean insertLast(int value) {
if (isFull()) return false;
Node node = new Node(value);
if (isEmpty()) {
last = node;
first = last;
}else {
Node oldLast = last;
last = node;
last.next = first;
last.pre = oldLast;
first.pre = last;
oldLast.next = last;
}
N++;
return true;
}
public boolean deleteFront() {
if (isEmpty()) return false;
if (size()==1) {
first=null;
last =null;
}else {
Node oldFirst = first;
first = oldFirst.next;
first.pre = last;
last.next = first;
}
N--;
return true;
}
public boolean deleteLast() {
if (isEmpty()) return false;
if (size()==1) {
first = null;
last = null;
}else {
Node oldLast = last;
last = oldLast.pre;
last.next = first;
first.pre = last;
}
N--;
return true;
}
public int getFront() {
if (isEmpty()) return -1;
return first.value;
}
public int getRear() {
if (isEmpty()) return -1;
return last.value;
}
public int size() {
return N;
}
public boolean isEmpty() {
return size() == 0;
}
public boolean isFull() {
return size()==capacity;
}
}
六、42. 接雨水
6.1 解法一：使用栈来解决
public int trap(int[] height) {
if (height==null || height.length<3) return 0;
Deque<Integer> deque = new LinkedList<>();
int container = 0;
for (int i=0; i<height.length; i++) {
while (!deque.isEmpty() && height[i]>height[deque.peek()]) {
int lo = deque.removeFirst();
if (deque.isEmpty()) break;
int left = deque.peek();
int width = i - left - 1;
int high = Math.min(height[i], height[left])-height[lo];
container += width * high;
}
deque.addFirst(i);
}
return container;
}