- 316.去除重复字母
(https://leetcode-cn.com/problems/remove-duplicate-letters)
image
String removeDuplicateLetters(String s) {
Stack<Character> stk = new Stack<>();
// 维护一个计数器记录字符串中字符的数量
// 因为输入为 ASCII 字符，大小 256 够用了
int[] count = new int[256];
for (int i = 0; i < s.length(); i++) {
count[s.charAt(i)]++;
}
boolean[] inStack = new boolean[256];
for (char c : s.toCharArray()) {
// 每遍历过一个字符，都将对应的计数减一
count[c]--;
if (inStack[c]) continue;
while (!stk.isEmpty() && stk.peek() > c) {
// 若之后不存在栈顶元素了，则停止 pop
if (count[stk.peek()] == 0) {
break;
}
// 若之后还有，则可以 pop
inStack[stk.pop()] = false;
}
stk.push(c);
inStack[c] = true;
}
StringBuilder sb = new StringBuilder();
while (!stk.empty()) {
sb.append(stk.pop());
}
return sb.reverse().toString();
}
这里也可以想到为什么要用「栈」这种数据结构，因为先进后出的结构允许我们立即操作刚插入的字符，如果用「队列」的话肯定是做不到的。
-
移掉K位数字
截屏2021-11-24 下午7.03.05.png
我们可以用一个栈维护当前的答案序列，栈中的元素代表截止到当前位置，删除不超过 kk 次个数字后，所能得到的最小整数。
class Solution {
public String removeKdigits(String num, int k) {
if(k == 0) return num;
if(k == num.length()) return "0";
Stack<Character> s = new Stack<>();
int index = 0;
while(index < num.length()){
while(k > 0 && s.size() > 0 && num.charAt(index) < s.peek()){
s.pop();
k--;
}
//前导0情况的处理
if(s.size() == 0 && num.charAt(index) == '0') {
index++;
continue;
}
s.push(num.charAt(index));
index++;
}
String ans = "";
while(k > 0){
s.pop();
k--;
}
if(s.size() == 0) return "0";
while(!s.isEmpty()) ans += s.pop();
return new StringBuffer(ans).reverse().toString();
}
}
- 拼接最大数
和第一道题类似，只不过这一次是两个数组，而不是一个，并且是求最大数。
最大最小是无关紧要的，关键在于是两个数组，并且要求从两个数组选取的元素个数加起来一共是 k。
然而在一个数组中取 k 个数字，并保持其最小（或者最大），我们已经会了（利用单调栈）。但是如果问题扩展到两个，会有什么变化呢？
实际上，问题本质并没有发生变化。 假设我们从 nums1 中取了 k1 个，从 num2 中取了 k2 个，其中 k1 + k2 = k。而 k1 和 k2 这 两个子问题我们是会解决的。由于这两个子问题是相互独立的，因此我们只需要分别求解，然后将结果合并即可。
假如 k1 和 k2 个数字，已经取出来了。那么剩下要做的就是将这个长度分别为 k1 和 k2 的数字，合并成一个长度为 k 的数组合并成一个最大的数组。
以题目的 nums1 = [3, 4, 6, 5] nums2 = [9, 1, 2, 5, 8, 3] k = 5 为例。 假如我们从 num1 中取出 1 个数字，那么就要从 nums2 中取出 4 个数字。
运用第一题的方法，我们计算出应该取 nums1 的 [6]，并取 nums2 的 [9,5,8,3]。 如何将 [6] 和 [9,5,8,3]，使得数字尽可能大，并且保持相对位置不变呢？
实
class Solution {
public int[] maxNumber(int[] nums1, int[] nums2, int k) {
int m = nums1.length;
int n = nums2.length;
int[] ans = new int[k];
int len = Math.min(k, m);
for (int i=Math.max(0, k-n); i<=len; i++) {
int[] sub1 = maxKArray(nums1, i);
int[] sub2 = maxKArray(nums2, k-i);
int[] array = combineArray(sub1, sub2, k);
for (int j=0; j<k; j++) {
if (array[j] == ans[j]) continue;
if (array[j] > ans[j]) ans = array;
break;
}
}
return ans;
}
public int[] maxKArray(int[] nums, int k) {
if (k == 0) return new int[0];
int[] res = new int[k];
int cursor = -1;
for (int i=0; i<nums.length; i++) {
while (cursor>=0 && nums[i]>res[cursor] && nums.length-i>k-cursor-1) {
cursor--;
}
if (cursor < k-1)
res[++cursor] = nums[i];
}
return res;
}
public int[] combineArray(int[] nums1, int[] nums2, int k) {
int[] res = new int[k];
int i = 0;
int i1 = 0;
int i2 = 0;
while (i1 < nums1.length && i2 < nums2.length)
res[i++] = deepCompare(nums1, nums2, i1, i2)? nums1[i1++] : nums2[i2++];
while (i1 < nums1.length)
res[i++] = nums1[i1++];
while (i2 < nums2.length)
res[i++] = nums2[i2++];
return res;
}
public boolean deepCompare(int[] nums1, int[] nums2, int i1, int i2) {
while (i1 < nums1.length && i2 < nums2.length) {
if (nums1[i1] == nums2[i2]) {
i1++;
i2++;
continue;
}
return nums1[i1] > nums2[i2];
}
return i1 < nums1.length;
}
}
- Largest Rectangle in Histogram
我们归纳一下枚举「高」的方法：
首先我们枚举某一根柱子 i 作为高h=heights[i]；
随后我们需要进行向左右两边扩展，使得扩展到的柱子的高度均不小于 h。换句话说，我们需要找到左右两侧最近的高度小于 h 的柱子，这样这两根柱子之间（不包括其本身）的所有柱子高度均不小于 h，并且就是 ii 能够扩展到的最远范围。
这样我们在枚举到第 i 根柱子的时候，就可以先把所有高度大于等于 height[i] 的 j 值全部移除，剩下的 j 值中高度最高的即为答案。在这之后，我们将 i 放入数据结构中，开始接下来的枚举。此时，我们需要使用的数据结构也就呼之欲出了，它就是栈。
栈中存放了 j 值。从栈底到栈顶，j 的值严格单调递增，同时对应的高度值也严格单调递增；
当我们枚举到第 ii 根柱子时，我们从栈顶不断地移除 height[j]≥height[i] 的 j 值。在移除完毕后，栈顶的 j 值就一定满足 height[j]<height[i]，此时 j 就是 i 左侧且最近的小于其高度的柱子。
这里会有一种特殊情况。如果我们移除了栈中所有的 j 值，那就说明 i 左侧所有柱子的高度都大于 height[i]，那么我们可以认为 i 左侧且最近的小于其高度的柱子在位置 j=−1，它是一根「虚拟」的、高度无限低的柱子。这样的定义不会对我们的答案产生任何的影响，我们也称这根「虚拟」的柱子为「哨兵」。
我们再将 i 放入栈顶。
栈中存放的元素具有单调性，这就是经典的数据结构「单调栈」了。
复杂度分析:
时间复杂度：O(N)。
空间复杂度：O(N)。
class Solution {
public int largestRectangleArea(int[] heights) {
int n = heights.length;
int[] left = new int[n];
int[] right = new int[n];
Deque<Integer> mono_stack = new ArrayDeque<Integer>();
for (int i = 0; i < n; ++i) {
while (!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {
mono_stack.pop();
}
left[i] = (mono_stack.isEmpty() ? -1 : mono_stack.peek());
mono_stack.push(i);
}
mono_stack.clear();
for (int i = n - 1; i >= 0; --i) {
while (!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {
mono_stack.pop();
}
right[i] = (mono_stack.isEmpty() ? n : mono_stack.peek());
mono_stack.push(i);
}
int ans = 0;
for (int i = 0; i < n; ++i) {
ans = Math.max(ans, (right[i] - left[i] - 1) * heights[i]);
}
return ans;
}
}
- Maximal Rectangle
我们首先计算出矩阵的每个元素的左边连续 1的数量，使用二维数组 left 记录，其中left[i][j] 为矩阵第 i行第 j 列元素的左边连续 1的数量。
class Solution {
public int maximalRectangle(char[][] matrix) {
int m = matrix.length;
if (m == 0) {
return 0;
}
int n = matrix[0].length;
int[][] left = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == '1') {
left[i][j] = (j == 0 ? 0 : left[i][j - 1]) + 1;
}
}
}
int ret = 0;
for (int j = 0; j < n; j++) { // 对于每一列，使用基于柱状图的方法
int[] up = new int[m];
int[] down = new int[m];
Deque<Integer> stack = new LinkedList<Integer>();
for (int i = 0; i < m; i++) {
while (!stack.isEmpty() && left[stack.peek()][j] >= left[i][j]) {
stack.pop();
}
up[i] = stack.isEmpty() ? -1 : stack.peek();
stack.push(i);
}
stack.clear();
for (int i = m - 1; i >= 0; i--) {
while (!stack.isEmpty() && left[stack.peek()][j] >= left[i][j]) {
stack.pop();
}
down[i] = stack.isEmpty() ? m : stack.peek();
stack.push(i);
}
for (int i = 0; i < m; i++) {
int height = down[i] - up[i] - 1;
int area = height * left[i][j];
ret = Math.max(ret, area);
}
}
return ret;
}
}
