左神算法学习笔记 - 015【入门】栈的入门题目-最小栈

【算法讲解015【入门】栈的入门题目-最小栈】 https://www.bilibili.com/video/BV15X4y177cM/?share_source=copy_web&vd_source=939a5033dc1ec4f712d59a4a4042e169

leetcode

这道题所谓最小栈，实际上是希望在普通栈操作的基础上，提供一个「得到栈中最小值」的方法，能够在任何时候调用它得到当前栈的最小值。

解法是非常精妙的。

如评论区有人留言所说：算法做多了感觉就是时间换空间。

这道题如果笨办法做的话，确实时间复杂度比较低：

• 左神简单描述了一下，比如用遍历来解，那就是每次找 min 的时候遍历一下栈，然后下次弹出的话再次遍历，显然不是最优解。而且我觉得遍历栈也是比较麻烦的事。

• 另外，我想到，既然是需要「任何时候得到一个集合的最小值」，可以使用小根堆，在操作栈的同时，同步操作小根堆就可以了。这样可以通过，但是时间复杂度不好。

左神讲解的方法比较精妙，大概意思如下：

• 在数据栈之外，同步维护一个最小栈，这个最小栈的栈顶用来代表「当前数据状况下，数据栈中的最小值」

• 如何维护这个最小栈是关键

  • 当插入数据时，数据栈插入，最小栈对比「新数据」和「栈顶数据」，如果新数据更小则插入，如果不是更小，重复插入一遍栈顶元素（意味着它还是最小的那个）

  • 当弹出数据的时候，数据栈和最小栈同步弹出

也就是通过额外的一个栈 + 一个精妙的规则，让我们方便地得到了 getMin() 这个功能。

使用 Stack 类实现的代码：

class MinStack1 {
		public Stack<Integer> data;
		public Stack<Integer> min;

		public MinStack1() {
			data = new Stack<Integer>();
			min = new Stack<Integer>();
		}

		public void push(int val) {
			data.push(val);
			if (min.isEmpty() || val <= min.peek()) {
				min.push(val);
			} else { // !min.isEmpty() && val > min.peek()
				min.push(min.peek());
			}
		}

		public void pop() {
			data.pop();
			min.pop();
		}

		public int top() {
			return data.peek();
		}

		public int getMin() {
			return min.peek();
		}
	}

当然，使用语言自己的栈，还是相对较慢，对于栈来说，我们可以根据数据量自己用数组 + size 变量实现：

class MinStack2 {
		// leetcode的数据在测试时，同时在栈里的数据不超过这个值
		// 这是几次提交实验出来的，哈哈
		// 如果leetcode补测试数据了，超过这个量导致出错，就调大
		public final int MAXN = 8001;

		public int[] data;
		public int[] min;
		int size;

		public MinStack2() {
			data = new int[MAXN];
			min = new int[MAXN];
			size = 0;
		}

		public void push(int val) {
			data[size] = val;
			if (size == 0 || val <= min[size - 1]) {
				min[size] = val;
			} else {
				min[size] = min[size - 1];
			}
			size++;
		}

		public void pop() {
			size--;
		}

		public int top() {
			return data[size - 1];
		}

		public int getMin() {
			return min[size - 1];
		}
	}

• 注意 size - 1 这种操作