Java 第 38 课 503.下一个更大元素II 402. 移掉 K 位数字

第 38 课

• 503.下一个更大元素II
• 402. 移掉 K 位数字

503.下一个更大元素II

Leetcode
循环数组

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        n = len(nums)
        res, q = [-1] * n, []
        for i in range(2 * n, -1, -1):
            num = nums[i % n]
            while q and num >= q[-1]: q.pop() # 栈顶元素正好比当前元素大，栈保存右边的元素。
            if q: res[i % n] = q[-1]
            q.append(num)
            
        return res

class Solution {
    public int[] nextGreaterElements(int[] nums) {
    	int n = nums.length;
		Deque<Integer> stack = new ArrayDeque<>();
		int[] ans = new int[n];
		for (int i = 2 * n - 1; i >= 0; i--){ // 逆序, 长度翻倍
            int num = nums[i % n];
			while (!stack.isEmpty() && stack.peek() <= num){ 
				stack.pop();
			} 
			ans[i % n] = stack.isEmpty() ? -1 : stack.peek();
			stack.push(num);
		}
		return ans;
    }
}

402. 移掉 K 位数字

Leetcode

class Solution(object):
    def removeKdigits(self, num, k):
        stack, remain = [], len(num) - k
        for digit in num:
            while k and stack and stack[-1] > digit:
                stack.pop()
                k -= 1
            stack.append(digit)
            
        return ''.join(stack[:remain]).lstrip('0') or '0'

class Solution {
    public String removeKdigits(String num, int k) {
        int n = num.length(), r = n - k, m = 0;
        if(k >= n) return "0"; // 全部删除直接返回 "0" 
        StringBuilder stack = new StringBuilder(); // 模拟栈
        for(char c : num.toCharArray()){
            while (m > 0 && k > 0 && stack.charAt(m - 1) > c){
                stack.deleteCharAt(m - 1); m--; k--;             
            }
            stack.append(c); 
            m++; // 记录 stack.length()          
        }        
        String res = stack.toString().substring(0, r);
        int i = 0; 
        for (;i < res.length(); i++)
            if(res.charAt(i) != '0') break;
        return i == res.length() ? "0" : res.substring(i);
    }
}