496. 下一個更大元素 I
題目描述
給定兩個沒有重復(fù)元素 的數(shù)組 nums1 和 nums2 乞榨，其中nums1 是 nums2 的子集。
找到 nums1 中每個元素在 nums2 中的下一個比其大的值。
nums1 中數(shù)字 x 的下一個更大元素是指 x 在 nums2 中對應(yīng)位置的右邊的第一個
比 x 大的元素澈蟆。如果不存在吩蔑，對應(yīng)位置輸出 -1 昔期。
示例 1:
輸入: nums1 = [4,1,2], nums2 = [1,3,4,2].
輸出: [-1,3,-1]
解釋:
對于num1中的數(shù)字4犁功，你無法在第二個數(shù)組中找到下一個更大的數(shù)字趣避，因此輸出 -1晚顷。
對于num1中的數(shù)字1峰伙，第二個數(shù)組中數(shù)字1右邊的下一個較大數(shù)字是 3。
對于num1中的數(shù)字2该默，第二個數(shù)組中沒有下一個更大的數(shù)字瞳氓，因此輸出 -1。
示例 2:
輸入: nums1 = [2,4], nums2 = [1,2,3,4].
輸出: [3,-1]
解釋:
對于 num1 中的數(shù)字 2 栓袖，第二個數(shù)組中的下一個較大數(shù)字是 3 匣摘。
對于 num1 中的數(shù)字 4 店诗，第二個數(shù)組中沒有下一個更大的數(shù)字，因此輸出 -1 音榜。
提示：
nums1和nums2中所有元素是唯一的庞瘸。
nums1和nums2 的數(shù)組大小都不超過1000。
Related Topics 棧
暴力解法最容易想到囊咏，而且相對來說理解簡單：
class Solution:
def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
# 暴力解法
res = []
for num1 in nums1:
for i in range(nums2.index(num1)+1, len(nums2)):
if nums2[i] > num1:
res.append(nums2[i])
break
else:
res.append(-1)
return res
其時間復(fù)雜度為 恕洲，而優(yōu)化方法便是單調(diào)棧。若把數(shù)組看成不同高度的人的排隊結(jié)果梅割，每個元素的下一個更大的元素便是他回頭看到的第一個高個子霜第。中間的矮個兒即可忽略（也即被擋住）户辞。
解題中需要注意的是入棧順序是倒敘泌类。因此下一個元素入棧前比其小的元素均要出棧，因為這些元素均是在這個元素的后面底燎，這個元素入棧后比其小的元素均被其擋住刃榨。
class Solution:
def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
hashmap = {}
stack = []
for i in range(len(nums2)-1, -1, -1):
while stack and stack[-1] < nums2[i]:
stack.pop()
hashmap[nums2[i]] = -1 if not stack else stack[-1]
stack.append(nums2[i])
# print(hashmap)
res = []
for num in nums1:
res.append(hashmap[num])
return res
單調(diào)棧解法時間復(fù)雜度為 ，因為對于每個元素來說双仍，最多只有入棧和出棧兩個操作枢希。
503. 下一個更大元素 II
題目描述
給定一個循環(huán)數(shù)組（最后一個元素的下一個元素是數(shù)組的第一個元素），輸出每個元素的下一個更大元素朱沃。
數(shù)字 x 的下一個更大的元素是按數(shù)組遍歷順序苞轿，這個數(shù)字之后的第一個比它更大的數(shù)，這意味著你應(yīng)該循
環(huán)地搜索它的下一個更大的數(shù)逗物。如果不存在搬卒，則輸出 -1。
示例 1:
輸入: [1,2,1]
輸出: [2,-1,2]
解釋: 第一個 1 的下一個更大的數(shù)是 2翎卓；
數(shù)字 2 找不到下一個更大的數(shù)契邀；
第二個 1 的下一個最大的數(shù)需要循環(huán)搜索，結(jié)果也是 2失暴。
注意: 輸入數(shù)組的長度不會超過 10000坯门。
Related Topics 棧
對于循環(huán)數(shù)組元素的下一個元素就不僅僅是其右邊的元素了，也可能是其左邊的元素逗扒。為了實現(xiàn)能同時搜索其左右元素古戴，我們可以將原數(shù)組復(fù)制一份加入到原數(shù)組的后面，然后按照 496. 下一個更大元素 I 的解法：
class Solution:
def nextGreaterElements(self, nums: List[int]) -> List[int]:
# 利用 496.下一個更大元素I 中的解法缴阎，將數(shù)組復(fù)制一份加入到原數(shù)組后面
stack = []
nums = nums + nums
n = len(nums)
res = [-1] * n
for i in range(n-1, -1, -1):
while stack and stack[-1] <= nums[i]:
stack.pop()
res[i] = -1 if not stack else stack[-1]
stack.append(nums[i])
# print(res)
return res[:n//2]
在實際中面對循環(huán)數(shù)組允瞧，一般是采用取余 (%) 來實現(xiàn)。所以本題中我們也可以不復(fù)制數(shù)組，而采用取余來實現(xiàn)：
class Solution:
def nextGreaterElements(self, nums: List[int]) -> List[int]:
stack = []
n = len(nums)
res = [-1] * n
for i in range(2*n-1, -1, -1):
while stack and stack[-1] <= nums[i % n]:
stack.pop()
res[i % n] = -1 if not stack else stack[-1]
stack.append(nums[i % n])
# print(res)
return res
402. 移掉K位數(shù)字
給定一個以字符串表示的非負(fù)整數(shù) num述暂，移除這個數(shù)中的 k 位數(shù)字痹升，使得剩下的數(shù)字最小。
注意:
num 的長度小于 10002 且 ≥ k畦韭。
num 不會包含任何前導(dǎo)零疼蛾。
示例 1 :
輸入: num = "1432219", k = 3
輸出: "1219"
解釋: 移除掉三個數(shù)字 4, 3, 和 2 形成一個新的最小的數(shù)字 1219。
示例 2 :
輸入: num = "10200", k = 1
輸出: "200"
解釋: 移掉首位的 1 剩下的數(shù)字為 200. 注意輸出不能有任何前導(dǎo)零艺配。
示例 3 :
輸入: num = "10", k = 2
輸出: "0"
解釋: 從原數(shù)字移除所有的數(shù)字察郁，剩余為空就是0。
Related Topics 棧 貪心算法
題目分析
首先我們需要確定什么樣的數(shù)字應(yīng)該被移除转唉。當(dāng)我們考察位置 的數(shù)字時皮钠，若其前面有數(shù)字，如果移除前面的數(shù)字能獲得更小的結(jié)果赠法，那前面的數(shù)字應(yīng)該被移除麦轰。由于每次對比都是臨近的數(shù)字，則考慮使用棧來解決問題砖织。
class Solution:
def removeKdigits(self, num: str, k: int) -> str:
n = len(num)
if n == k:
return '0'
stack = []
for c in num:
while stack and stack[-1] > c and k > 0:
stack.pop()
k -= 1
if not stack and c == '0':
continue
stack.append(c)
# 還有要刪除的元素款侵，就從棧頂刪除
for _ in range(k):
stack.pop()
return '0' if not stack else ''.join(stack)
1081. 不同字符的最小子序列
題目描述
返回字符串 text 中按字典序排列最小的子序列，該子序列包含 text 中所有不同字符一次侧纯。
示例 1：
輸入："cdadabcc"
輸出："adbc"
示例 2：
輸入："abcd"
輸出："abcd"
示例 3：
輸入："ecbacba"
輸出："eacb"
示例 4：
輸入："leetcode"
輸出："letcod"
提示：
1 <= text.length <= 1000
text 由小寫英文字母組成
注意：本題目與 316 https://leetcode-cn.com/problems/remove-duplicate-letters/ 相同
Related Topics 棧 貪心算法 字符串
題目分析
本題需要考慮的重點是怎么確定該字符是否需要刪除新锈。如果后面還有該字符，則前面比當(dāng)前大的字符應(yīng)該被刪除眶熬，以保留字典序最小的結(jié)果妹笆。鑒于此，我們考慮對所有字符進(jìn)行計數(shù)聋涨，用于判斷后面是否還有該字符晾浴。
class Solution:
def smallestSubsequence(self, s: str) -> str:
# 計數(shù)
hashmap = {}
for c in s:
hashmap.setdefault(c, 0)
hashmap[c] += 1
stack = []
inStack = {}
for c in s:
hashmap[c] -= 1
if inStack.get(c):
continue
while stack and stack[-1] > c:
if hashmap[stack[-1]] == 0:
break
inStack[stack.pop()] = False
stack.append(c)
inStack[c] = True
return ''.join(stack)
321. 拼接最大數(shù)
題目描述
給定長度分別為 m 和 n 的兩個數(shù)組负乡，其元素由 0-9 構(gòu)成牍白，表示兩個自然數(shù)各位上的數(shù)字。
現(xiàn)在從這兩個數(shù)組中選出 k (k <= m + n) 個數(shù)字拼接成一個新的數(shù)抖棘，要求從同一個數(shù)組中
取出的數(shù)字保持其在原數(shù)組中的相對順序茂腥。
求滿足該條件的最大數(shù)。結(jié)果返回一個表示該最大數(shù)的長度為 k 的數(shù)組切省。
說明: 請盡可能地優(yōu)化你算法的時間和空間復(fù)雜度最岗。
示例 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]
Related Topics 貪心算法 動態(tài)規(guī)劃
本題留著挑戰(zhàn)吧。
