单调栈进阶: 去除重复字母/拼接最大数/最大矩形
Author：zhoulujun Date：
上一篇 《单调栈模板：下一个更大元素/每日温度/移掉K位数字/接雨水》，本篇再来几题
去除重复字母
给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
示例 1：输入：s = "bcabc" 输出："abc"
示例 2：输入：s = "cbacdcbc" 输出："acdb"
这个首先想到是 哈希表去重，但是此题目的三个要求：去重、不能打乱其他字符顺序、字典序最小。
去重：可以通过 「使用哈希表存储字母出现次数」 的方式，将每个字母出现的次数统计起来，再遍历一遍，去除重复的字母。
不能打乱其他字符顺序：按顺序遍历，将非重复的字母存储到答案数组或者栈中，最后再拼接起来，就能保证不打乱其他字符顺序。
字典序最小：意味着字典序小的字母应该尽可能放在前面。
对于第 i 个字符 s[i] 而言，如果第 0 ~ i - 1 之间的某个字符 s[j] 在 s[i] 之后不再出现了，那么 s[j] 必须放到 s[i] 之前。
而如果 s[j] 在之后还会出现，并且 s[j] 的字典序大于 s[i]，我们则可以先舍弃 s[j]，把 s[i] 尽可能的放到前面。后边再考虑使用 s[j] 所对应的字符。
这个可以参考 《单调栈模板：下一个更大元素/每日温度/移掉K位数字/接雨水》中的 移掉K位数字，只是这道题没有一个全局的删除次数 k。而是对于每一个在字符串 str 中出现的字母 letter都有一个 k 值。这个 k 是 字母letter 出现次数 - 1。
核心都是需要如何判断相同长度的字符串哪个的字典序更大。
与402.移掉K位数字 题目不同的是，这里需要满足同一种字符都需要出现，且只能出现一次。那怎么才能满足这些条件呢？
因此，需要额外考虑以下两个问题：
在考虑字符 s[i] 时，如果它已经存在于栈中，则不能加入字符 s[i]到单调栈中。为此，需要记录每个字符是否出现在栈中。
在弹出栈顶字符时，如果字符串在后面的位置上再也没有这一字符，则不能弹出栈顶字符。为此，需要记录每个字符的剩余数量，当这个值为 0 时，就不能弹出栈顶字符了。
function removeDuplicateLetters(s) {
const seen = new Map(); // 哈希表记录每个字符出现的次数
const stack = []; // 单调栈
for (let i = 0; i < s.length; i++) {
const ch = s[i];
if (!seen.has(ch)) {
while (stack.length > 0 && stack[stack.length - 1] > ch && seen.get(stack[stack.length - 1]) > 1) {
stack.pop();
}
stack.push(ch);
seen.set(ch, 1);
} else {
seen.set(ch, seen.get(ch) + 1);
}
}
let result = "";
while (stack.length > 0) {
result = stack.pop() + result;
}
return result;
}拼接最大数
给你两个整数数组 nums1 和 nums2，它们的长度分别为 m 和 n。数组 nums1 和 nums2 分别代表两个数各位上的数字。同时你也会得到一个整数 k。
请你利用这两个数组中的数字中创建一个长度为 k <= m + n 的最大数，在这个必须保留来自同一数组的数字的相对顺序。
返回代表答案的长度为 k 的数组。
示例 1： 输入：nums1 = [3,4,6,5], nums2 = [9,1,2,5,8,3], k = 5 输出：[9,8,6,5,3]
示例 2： 输入：nums1 = [6,7], nums2 = [6,0,4], k = 5 输出：[6,7,6,0,4]
示例 3： 输入：nums1 = [3,9], nums2 = [8,9], k = 3 输出：[9,8,9]
最大数可以是：
最大数全部在 nums1 中
最大数全部在 nums2 中
最大数部分在 nums1 中，部分在 nums2 中； 所以此处需要一个枚举；
在 nums1 中找 i 个最大值并在 nums2 找 k−i 个最大值组成的所有可能的最大值即位题目答案
很显然这可以用单调栈来优化，整个算法就分成三步：
分别计算 num1 和 nums2 的最大子序列
按照字典序降序合并子序列
保存对应的整数较大的子序列
function maxNumber(nums1, nums2, k) {
const maxSubsequence = (nums, k) => {
const stack = [];
let drop = nums.length - k;
for (let num of nums) {
while (drop > 0 && stack.length > 0 && stack[stack.length - 1] < num) {
stack.pop();
drop--;
}
stack.push(num);
}
return stack.slice(0, k);
};
const merge = (nums1, nums2) => {
const mergeArray = (arr1, arr2) => {
const merged = [];
while (arr1.length + arr2.length > 0) {
let bigger = arr1 > arr2 ? arr1 : arr2;
merged.push(bigger.shift());
}
return merged;
};
const result = [];
while (nums1.length > 0 && nums2.length > 0) {
if (nums1 > nums2) {
result.push(nums1.shift());
} else {
result.push(nums2.shift());
}
}
result.push(...nums1, ...nums2);
return result;
};
let maxResult = [];
for (let i = Math.max(0, k - nums2.length); i <= Math.min(k, nums1.length); i++) {
const candidate = merge(maxSubsequence(nums1, i), maxSubsequence(nums2, k - i));
if (candidate > maxResult) {
maxResult = candidate;
}
}
return maxResult;
}柱状图中最大的矩形
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
示例 1: 输入：heights = [2,1,5,6,2,3] 输出：10 解释：最大的矩形为图中红色区域，面积为 10
本题最好的解释：https://www.cnblogs.com/GarrettWale/p/15796780.html
暴力法-超时
这道问题的暴力解法比「接雨水」那道题要其实好想得多：可以枚举以每个柱形为高度的最大矩形的面积。
要想找到第 i 位置最大面积是什么？
是以 i 为中心，向左找第一个小于 heights[i] 的位置 left_i；向右找第一个小于于 heights[i] 的位置 right_i，即最大面积为 heights[i] * (right_i - left_i -1)，如下图所示：
所以，我们的问题就变成如何找right_i 和 left_i？最简单的思路就是，就是暴力法，直接分别在 i 左右移动。
具体来说是：依次遍历柱形的高度，对于每一个高度分别向两边扩散，求出以当前高度为矩形的最大宽度多少。
为此，我们需要：
左边看一下，看最多能向左延伸多长，找到大于等于当前柱形高度的最左边元素的下标；
右边看一下，看最多能向右延伸多长；找到大于等于当前柱形高度的最右边元素的下标。
对于每一个位置，我们都这样操作，得到一个矩形面积，求出它们的最大值。
function largestRectangleArea(heights) {
const n = heights.length;
let maxArea = -Infinity;
for (let i = 0; i < n; i++) {
const currentHeight = heights[i];
let left = i;
while (left >= 0 && heights[left] >= currentHeight) {
left--;
}
let right = i;
while (right < n && heights[right] >= currentHeight) {
right++;
}
maxArea = Math.max(maxArea, (right - left - 1) * currentHeight);
}
return maxArea;
}两种暴力方法的时间复杂度均为 O(N^2 )，会超出时间限制，我们必须要进行优化。
单调栈
如何快速计算 left 和 right？这可以用单调栈求出。
var largestRectangleArea = function(heights) {
const n = heights.length; // 获取柱状图的高度数组长度
const leftArr = Array(n).fill(-1);// 用于存储每个柱形左侧第一个比它矮的柱形的索引；初始化-1，表示没有更矮的柱形在左侧
const stack = [];
for (let i = 0; i < n; i++) {//初始化为n（表示没有更矮的柱形在右侧）
const x = heights[i]; // 当前柱形的高度
//当栈不为空且当前柱子高度小于等于栈顶柱子的高度时，出栈
while (stack.length && x <= heights[stack[stack.length - 1]]) {
stack.pop();
}
if (stack.length) { // 如果栈不为空，说明找到了左边第一个比当前柱子矮的柱子，将其索引存入leftArr
leftArr[i] = stack[stack.length - 1];
}
stack.push(i); // 将当前柱形索引压入栈中
}
const rightArr = Array(n).fill(n);//用于存储每个柱子右边第一个比它矮的柱子的索引,初始化为n（表示没有更矮的柱形在右侧）
stack.length = 0; // 清空栈，重新利用栈来计算rightArr
for (let i = n - 1; i >= 0; i--) {
const x = heights[i];
while (stack.length && x <= heights[stack[stack.length - 1]]) {// 同上，但方向相反
stack.pop();
}
if (stack.length) {
rightArr[i] = stack[stack.length - 1];
}
stack.push(i);
}
let ans = 0; // 初始化最大矩形面积为0
for (let i = 0; i < n; i++) { // 遍历每个柱形，计算以其高度为高的最大矩形面积，并更新最大面积
ans = Math.max(ans, heights[i] * (rightArr[i] - leftArr[i] - 1));
}
return ans;
};单调栈+哨兵机制
考虑到枚举「宽」的方法使用了两重循环，本身就已经需要 O(N ^2) 的时间复杂度，不容易优化，因此我们可以考虑优化只使用了一重循环的枚举「高」的方法。
var largestRectangleArea = function(heights) {
let maxArea = 0;
const stack = [];// 维护一个单调递增栈
heights = [0,...heights,0]; // 数组头部加入元素0 数组尾部加入元素0 ——为了避免最后队列中还存留一些元素
// 只用考虑情况一 当前遍历的元素heights[i]小于栈顶元素heights[stack[stack.length-1]]]的情况
for(let i = 0; i < heights.length; i++){
while(heights[i] < heights[stack[stack.length-1]]){// 当前bar比栈顶bar矮
const stackTopIndex = stack.pop();// 栈顶元素出栈，并保存栈顶bar的索引
let w = i - stack[stack.length -1] - 1;
let h = heights[stackTopIndex]
maxArea = Math.max(maxArea, w * h); // 计算面积，并取最大面积
}
stack.push(i);// 当前bar比栈顶bar高了，入栈
}
return maxArea;
};最大矩形
给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
示例 1： 输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]] 输出：6
思路：84题的变种，从第一行到第n行形成的柱状图可以利用84题求解，然后循环每一行，计算以这一行为底的柱状图最大面积，然后更新最大矩形面积
var maximalRectangle = function(matrix) {
const m = matrix.length;
if (m === 0) {
return 0;
}
const n = matrix[0].length;
const left = new Array(m).fill(0).map(() => new Array(n).fill(0));
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (matrix[i][j] === '1') {
left[i][j] = (j === 0 ? 0 : left[i][j - 1]) + 1;
}
}
}
let ret = 0;
for (let j = 0; j < n; j++) { // 对于每一列，使用基于柱状图的方法
const up = new Array(m).fill(0);
const down = new Array(m).fill(0);
let stack = new Array();
for (let i = 0; i < m; i++) {
while (stack.length && left[stack[stack.length - 1]][j] >= left[i][j]) {
stack.pop();
}
up[i] = stack.length === 0 ? -1 : stack[stack.length - 1];
stack.push(i);
}
stack = [];
for (let i = m - 1; i >= 0; i--) {
while (stack.length && left[stack[stack.length - 1]][j] >= left[i][j]) {
stack.pop();
}
down[i] = stack.length === 0 ? m : stack[stack.length - 1];
stack.push(i);
}
for (let i = 0; i < m; i++) {
const height = down[i] - up[i] - 1;
const area = height * left[i][j];
ret = Math.max(ret, area);
}
}
return ret;
};其实最简单还是动态规划来做，具体还是看《 岛屿算法（求岛屿数量与岛屿面积）》
参考文章：
用javascript分类刷leetcode13.单调栈(图文视频讲解) https://cloud.tencent.com/developer/article/2205708
[路飞]_321. 拼接最大数 https://juejin.cn/post/7071584649142599693
321. 拼接最大数 #https://howieyuen.github.io/docs/leetcode/0321/
321. 拼接最大数 java贪心题解 https://blog.csdn.net/qq_38409944/article/details/84678140
转载本站文章《单调栈进阶: 去除重复字母/拼接最大数/最大矩形》,
请注明出处：https://www.zhoulujun.cn/html/theory/algorithm/leetcode/9087.html