496. 下一個更大元素 I
題目描述
給定兩個沒有重復元素 的數(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
其時間復雜度為 ，而優(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)棧解法時間復雜度為 ，因為對于每個元素來說，最多只有入棧和出棧兩個操作。
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ù)組復制一份加入到原數(shù)組的后面，然后按照 496. 下一個更大元素 I 的解法：
class Solution:
def nextGreaterElements(self, nums: List[int]) -> List[int]:
# 利用 496.下一個更大元素I 中的解法，將數(shù)組復制一份加入到原數(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)。所以本題中我們也可以不復制數(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ù)字
給定一個以字符串表示的非負整數(shù) num，移除這個數(shù)中的 k 位數(shù)字，使得剩下的數(shù)字最小。
注意:
num 的長度小于 10002 且 ≥ k。
num 不會包含任何前導零。
示例 1 :
輸入: num = "1432219", k = 3
輸出: "1219"
解釋: 移除掉三個數(shù)字 4, 3, 和 2 形成一個新的最小的數(shù)字 1219。
示例 2 :
輸入: num = "10200", k = 1
輸出: "200"
解釋: 移掉首位的 1 剩下的數(shù)字為 200. 注意輸出不能有任何前導零。
示例 3 :
輸入: num = "10", k = 2
輸出: "0"
解釋: 從原數(shù)字移除所有的數(shù)字，剩余為空就是0。
Related Topics 棧 貪心算法
題目分析
首先我們需要確定什么樣的數(shù)字應(yī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 棧 貪心算法 字符串
題目分析
本題需要考慮的重點是怎么確定該字符是否需要刪除。如果后面還有該字符，則前面比當前大的字符應(yīng)該被刪除，以保留字典序最小的結(jié)果。鑒于此，我們考慮對所有字符進行計數(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)化你算法的時間和空間復雜度。
示例 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)吧。
