[TOC]
496. 下一個更大元素 I(簡單)
nums1 中數(shù)字 x 的 下一個更大元素 是指 x 在 nums2 中對應(yīng)位置 右側(cè) 的 第一個 比 x 大的元素。給你兩個 沒有重復(fù)元素 的數(shù)組 nums1 和 nums2 侈离，下標(biāo)從 0 開始計數(shù)款青，其中nums1 是 nums2 的子集。對于每個 0 <= i < nums1.length 霍狰，找出滿足 nums1[i] == nums2[j] 的下標(biāo) j 抡草，并且在 nums2 確定 nums2[j] 的 下一個更大元素 。如果不存在下一個更大元素蔗坯，那么本次查詢的答案是 -1 康震。返回一個長度為 nums1.length 的數(shù)組 ans 作為答案，滿足 ans[i] 是如上所述的 下一個更大元素 宾濒。
輸入：nums1 = [4,1,2], nums2 = [1,3,4,2].
輸出：[-1,3,-1]
解釋：nums1 中每個值的下一個更大元素如下所述：
- 4 腿短，用加粗斜體標(biāo)識，nums2 = [1,3,4,2]绘梦。不存在下一個更大元素橘忱，所以答案是 -1 。
- 1 卸奉，用加粗斜體標(biāo)識钝诚，nums2 = [1,3,4,2]。下一個更大元素是 3 榄棵。
- 2 凝颇，用加粗斜體標(biāo)識潘拱，nums2 = [1,3,4,2]。不存在下一個更大元素拧略，所以答案是 -1 芦岂。
輸入：nums1 = [2,4], nums2 = [1,2,3,4].
輸出：[3,-1]
解釋：nums1 中每個值的下一個更大元素如下所述：
- 2 ，用加粗斜體標(biāo)識垫蛆，nums2 = [1,2,3,4]禽最。下一個更大元素是 3 。
- 4 袱饭，用加粗斜體標(biāo)識弛随，nums2 = [1,2,3,4]。不存在下一個更大元素宁赤，所以答案是 -1 。
// =========== 倒序來 ===========
/*
古城算法思路栓票，倒序來
對于元素2决左，stack為空，不存在下一個更大元素走贪。因此Map中key=2,value=-1
接著佛猛，將元素2入棧，看它是否是前面某個元素的下一個更大元素坠狡。
對于元素4继找，stack不為空，但由于4大于棧頂元素2且在2前面逃沿，所以元素2不是前面某個元素的下一個更大元素婴渡，所以元素2出棧。對于元素4凯亮，key=4,value=-1
接著边臼，將元素4入棧，看它是否是前面某個元素的下一個更大元素假消。
對于元素3柠并，stack不為空，且棧頂元素4大于3富拗。對于元素3臼予，key=3,value=4
接著，將元素3入棧啃沪，看它是否是前面某個元素的下一個更大元素粘拾。
對于元素1，stack不為空创千，且棧頂元素3大于1半哟。key=1,value=3
接著酬滤，將元素1入棧。
此時nums2中所有元素考察完畢
對于數(shù)組nums1而言寓涨，對其遍歷盯串，拿考察元素作為Key，在map匯總就可以獲取到下一個更大元素了戒良。
1体捏、用哈希表m存儲每個數(shù)字的下一個最大數(shù)字
2、遍歷nums2糯崎，將數(shù)字壓入棧stack中
3几缭、一旦發(fā)現(xiàn)當(dāng)前nums2數(shù)字nums2[i]比棧頂數(shù)字要大，pop棧頂數(shù)字沃呢，更新棧頂元素的下一個最大數(shù)字值
4年栓、遍歷nums1，如果發(fā)現(xiàn)在m中有對應(yīng)的key薄霜，說明其由下一個最大數(shù)字某抓，返回這個數(shù)字；否則返回-1
*/
func nextGreaterElement_II(nums1 []int, nums2 []int) []int {
lenNums2 := len(nums2)
tempMap := make(map[int]int, lenNums2)
stack := make([]int, 0, lenNums2)
for i := lenNums2 - 1; i >= 0; i-- {
for len(stack) > 0 && nums2[i] >= stack[len(stack)-1] {
stack = stack[:len(stack)-1]
}
if len(stack) == 0 {
tempMap[nums2[i]] = -1 // 從后往前遍歷的時候惰瓜，key=最后一個元素否副，value=肯定等于-1
} else {
tempMap[nums2[i]] = stack[len(stack)-1]
}
stack = append(stack, nums2[i])
}
result := make([]int, 0, len(nums1))
for _, v := range nums1 {
result = append(result, tempMap[v])
}
return result
}
503. 下一個更大元素 II【中等】
給定一個循環(huán)數(shù)組 nums （ nums[nums.length - 1] 的下一個元素是 nums[0] ），返回 nums 中每個元素的 下一個更大元素 崎坊。數(shù)字 x 的 下一個更大的元素 是按數(shù)組遍歷順序备禀，這個數(shù)字之后的第一個比它更大的數(shù)，這意味著你應(yīng)該循環(huán)地搜索它的下一個更大的數(shù)奈揍。如果不存在曲尸，則輸出 -1 。
輸入: nums = [1,2,1]
輸出: [2,-1,2]
解釋: 第一個 1 的下一個更大的數(shù)是 2男翰；
數(shù)字 2 找不到下一個更大的數(shù)队腐；
第二個 1 的下一個最大的數(shù)需要循環(huán)搜索，結(jié)果也是 2奏篙。
輸入: nums = [1,2,3,4,3]
輸出: [2,3,4,-1,4]
// 古城算法柴淘，逆序操作
func nextGreaterElements(nums []int) []int {
nums = append(nums, nums...) // 擴(kuò)大數(shù)組，制作成一個基本單調(diào)棧用例
length := len(nums)
ans := make([]int, length)
var stack = make([]int, 0)
for i := length - 1; i >= 0; i-- {
for len(stack) > 0 && nums[i] >= stack[len(stack)-1] {
stack = stack[:len(stack)-1]
}
if len(stack) > 0 {
ans[i] = stack[len(stack)-1]
} else {
ans[i] = -1
}
stack = append(stack, nums[i])
}
return ans[0 : len(nums)/2]
}
739. 每日溫度【中等】
給定一個整數(shù)數(shù)組 temperatures 秘通，表示每天的溫度为严，返回一個數(shù)組 answer ，其中 answer[i] 是指對于第 i 天肺稀，下一個更高溫度出現(xiàn)在幾天后第股。如果氣溫在這之后都不會升高，請在該位置用 0 來代替话原。
輸入: temperatures = [73,74,75,71,69,72,76,73]
輸出: [1,1,4,2,1,1,0,0]
輸入: temperatures = [30,40,50,60]
輸出: [1,1,1,0]
輸入: temperatures = [30,60,90]
輸出: [1,1,0]
// 逆序遍歷夕吻，stack中存儲的是index诲锹，因為需要計算距離。
func dailyTemperatures(temperatures []int) []int {
length := len(temperatures)
ans := make([]int, length, length) // ans長度和容量都有
var stack = make([]int, 0, length) // 棧的長度為nil涉馅，有容量
for i := length - 1; i >= 0; i-- {
for len(stack) > 0 && temperatures[i] >= temperatures[stack[len(stack)-1]] {
stack = stack[:len(stack)-1]
}
if len(stack) > 0 {
ans[i] = stack[len(stack)-1] - i // 計算距離
} else {
ans[i] = 0
}
stack = append(stack, i) // stack中存儲的是index归园，因為需要計算距離。
}
return ans
}
42. 接雨水【困難】
給定 n 個非負(fù)整數(shù)表示每個寬度為 1 的柱子的高度圖稚矿，計算按此排列的柱子庸诱，下雨之后能接多少雨水。
輸入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
輸出：6
解釋：上面是由數(shù)組 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度圖晤揣，在這種情況下桥爽，可以接 6 個單位的雨水（藍(lán)色部分表示雨水）。
輸入：height = [4,2,0,3,2,5]
輸出：9
84. 柱狀圖中最大的矩形【困難】
給定 n 個非負(fù)整數(shù)昧识，用來表示柱狀圖中各個柱子的高度钠四。每個柱子彼此相鄰，且寬度為 1 跪楞。求在該柱狀圖中缀去，能夠勾勒出來的矩形的最大面積。
輸入：heights = [2,1,5,6,2,3]
輸出：10
解釋：最大的矩形為圖中紅色區(qū)域习霹，面積為 10
輸入： heights = [2,4]
輸出： 4
85. 最大矩形 【困難】
316. 去除重復(fù)字母（中等）
給你一個字符串 s ，請你去除字符串中重復(fù)的字母炫隶，使得每個字母只出現(xiàn)一次淋叶。需保證 返回結(jié)果的字典序最小（要求不能打亂其他字符的相對位置）伪阶。
輸入：s = "bcabc"
輸出："abc"
輸入：s = "cbacdcbc"
輸出："acdb"
363. 矩形區(qū)域不超過 K 的最大數(shù)值和【困難】
給你一個 m x n 的矩陣 matrix 和一個整數(shù) k 煞檩，找出并返回矩陣內(nèi)部矩形區(qū)域的不超過 k 的最大數(shù)值和。
題目數(shù)據(jù)保證總會存在一個數(shù)值和不超過 k 的矩形區(qū)域栅贴。
輸入：matrix = [[1,0,1],[0,-2,3]], k = 2
輸出：2
解釋：藍(lán)色邊框圈出來的矩形區(qū)域 [[0, 1], [-2, 3]] 的數(shù)值和是 2斟湃，且 2 是不超過 k 的最大數(shù)字（k = 2）。
輸入：matrix = [[2,2,-1]], k = 3
輸出：3
402. 移掉 K 位數(shù)字（中等）
給你一個以字符串表示的非負(fù)整數(shù) num 和一個整數(shù) k 檐薯，移除這個數(shù)中的 k 位數(shù)字凝赛，使得剩下的數(shù)字最小。請你以字符串形式返回這個最小的數(shù)字坛缕。
輸入：num = "1432219", k = 3
輸出："1219"
解釋：移除掉三個數(shù)字 4, 3, 和 2 形成一個新的最小的數(shù)字 1219 墓猎。
輸入：num = "10200", k = 1
輸出："200"
解釋：移掉首位的 1 剩下的數(shù)字為 200. 注意輸出不能有任何前導(dǎo)零。
輸入：num = "10", k = 2
輸出："0"
解釋：從原數(shù)字移除所有的數(shù)字赚楚，剩余為空就是 0 毙沾。
901. 股票價格跨度【中等】
962. 最大寬度坡（中等）
給定一個整數(shù)數(shù)組 A，坡是元組 (i, j)宠页，其中 i < j 且 A[i] <= A[j]左胞。這樣的坡的寬度為 j - i寇仓。找出 A 中的坡的最大寬度，如果不存在烤宙，返回 0 遍烦。
輸入：[6,0,8,2,1,5]
輸出：4
解釋：
最大寬度的坡為 (i, j) = (1, 5): A[1] = 0 且 A[5] = 5.
輸入：[9,8,1,0,1,9,4,0,4,1]
輸出：7
解釋：
最大寬度的坡為 (i, j) = (2, 9): A[2] = 1 且 A[9] = 1.
1081. 不同字符的最小子序列
255. 驗證前序遍歷序列二叉搜索樹（會員/中等）
1762. 能看到海景的建筑物（會員/中等）
有 n 座建筑物。給你一個大小為 n 的整數(shù)數(shù)組 heights 表示每一個建筑物的高度门烂。建筑物的右邊是海洋乳愉。如果建筑物可以無障礙地看到海洋，則建筑物能看到海景屯远。確切地說蔓姚，如果一座建筑物右邊的所有建筑都比它 矮 時，就認(rèn)為它能看到海景慨丐。返回能看到海景建筑物的下標(biāo)列表（下標(biāo) 從 0 開始 ）坡脐，并按升序排列。
輸入：heights = [4,2,3,1]
輸出：[0,2,3]
解釋：1 號建筑物看不到海景房揭，因為 2 號建筑物比它高
輸入：heights = [4,3,2,1]
輸出：[0,1,2,3]
解釋：所有的建筑物都能看到海景备闲。
1950. 所有子數(shù)組最小值中的最大值（會員/中等）
給你一個長度為 n 的整數(shù)數(shù)組 nums ，你需要處理 n 個查詢捅暴。對于第 i （0 <= i < n）個查詢：你需要先找出 nums 的所有長度為 i + 1 的子數(shù)組中的 最小值 恬砂。在這些最小值中找出 最大值 作為答案。返回一個 下標(biāo)從 0 開始 的長度為 n 的整數(shù)數(shù)組 ans 蓬痒，ans[i] 代表第 i 個查詢的答案泻骤。
輸入: nums = [0,1,2,4]
輸出: [4,2,1,0]
解釋:
i = 0:
- 大小為 1 的子數(shù)組為 [0], [1], [2], [4]
- 有最大的最小值的子數(shù)組是 [4], 它的最小值是 4
i = 1:
- 大小為 2 的子數(shù)組為 [0,1], [1,2], [2,4]
- 有最大的最小值的子數(shù)組是 [2,4], 它的最小值是 2
i = 2:
- 大小為 3 的子數(shù)組為 [0,1,2], [1,2,4]
- 有最大的最小值的子數(shù)組是 [1,2,4], 它的最小值是 1
i = 3:
- 大小為 4 的子數(shù)組為 [0,1,2,4]
- 有最大的最小值的子數(shù)組是 [0,1,2,4], 它的最小值是 0
輸入: nums = [10,20,50,10]
輸出: [50,20,10,10]
解釋:
i = 0:
- 大小為 1 的子數(shù)組為 [10], [20], [50], [10]
- 有最大的最小值的子數(shù)組是 [50], 它的最小值是 50
i = 1:
- 大小為 2 的子數(shù)組為 [10,20], [20,50], [50,10]
- 有最大的最小值的子數(shù)組是 [20,50], 它的最小值是 20
i = 2:
- 大小為 3 的子數(shù)組為 [10,20,50], [20,50,10]
- 有最大的最小值的子數(shù)組是 [10,20,50], 它的最小值是 10
i = 3:
- 大小為 4 的子數(shù)組為 [10,20,50,10]
- 有最大的最小值的子數(shù)組是 [10,20,50,10], 它的最小值是 10
