算法-CodeTop（二）字典序最大最小

字典序最大最小解题思路

字典序最大解题思路

维护一个栈

要保证字典序最小（大），我们从左往右遍历找出相邻的两个数

如果当前数比栈顶数小（大），根据条件判断是否弹出，根据不同的题进行不同的变化逻辑

如果不满足弹出条件则继续遍历

基本方法-合并两个数组得到最大顺序字典序

    //合并两个数组，生成字典序最大的组合
    private int[] merge(int[] nums1, int[] nums2) {

        int[] result = new int[nums1.length + nums2.length];
        int i = 0;//决定nums1的位置
        int j = 0;//决定nums2的位置
        int k = 0;//决定result的位置
        
        while (i < nums1.length || j < nums2.length) {
            if (greater(nums1, i, nums2, j)) {
                result[k++] = nums1[i++];
            } else {
                result[k++] = nums2[j++];
            }
        }
        
        return result;

    }

基本方法-从两个数组的指定位置比较字典序大小

    //比较两个数组从指定位置开始的字典序大小
    private boolean greater(int[] nums1, int i, int[] nums2, int j) {
        //跳过相同的值
        while (i < nums1.length && j < nums2.length && nums1[i] == nums2[j]) {
            i++;
            j++;
        }
        //结果取决于两个数组中第一个遇到的不同的数字
        //如果nums1【i】>nums2【j】返回ture
        //如果当 j == nums2.length ,则表示nums2 的子数组已经遍历完，但 nums1 还有剩余元素,说明nums1的字典序更大
        return j == nums2.length || (i < nums1.length && nums1[i] > nums2[j]);
    }

 402 移掉K位数字

题目

移除掉K位数字，使剩下的数字最小

思路解析

前置知识：

对于两个数 123a456 和 123b456，如果 a > b

那么数字 123a456 大于 数字 123b456，否则数字 123a456 小于等于数字 123b456

也就说，两个相同位数的数字大小关系取决于第一个不同的数的大小

因此我们的思路就是：

• 从左到右遍历
• 对于遍历到的元素，我们选择保留。
• 但是我们可以选择性丢弃前面相邻的元素

该题目算是贪心算法，从左往右遍历，从遍历时候的局部最优推出全局最优

代码

数组模拟栈

class Solution {
    public String removeKdigits(String num, int k) {

        // 使用数组模拟栈，存储最终保留的数字
        char[] stack = new char[num.length()];
        int top = 0; // 栈顶指针
        int remain = num.length() - k; // 最终需要保留的数字长度
        
        // 遍历输入字符串的每个字符
        for (char digit : num.toCharArray()) {
            // 当还有删除次数(k>0)，栈不为空(top>0)，且栈顶数字大于当前数字时
            // 弹出栈顶数字（相当于删除该数字），并减少删除次数k
            while (k > 0 && top > 0 && stack[top - 1] > digit) {
                top--; // 弹出栈顶元素
                k--;   // 减少删除次数
            }
            // 将当前数字压入栈中
            stack[top++] = digit;
        }
        
        // 处理前导零：找到第一个非零数字的位置
        int index = 0;
        while (index < remain && stack[index] == '0') {
            index++;
        }
        
        // 如果所有保留的数字都是0，返回"0"
        // 否则，从第一个非零数字开始构建结果字符串
        return index == remain ? "0" : new String(stack, index, remain - index);
        
    }
}

ArrayDeque

class Solution {
    public String removeKdigits(String num, int k) {

        // 处理特殊情况：k等于数字长度时直接返回"0"
        if (k >= num.length()) {
            return "0";
        }
        
        // 使用双端队列作为栈，存储构建的最小数字
        Deque<Character> stack = new ArrayDeque<>();
        
        // 遍历每个数字字符
        for (char digit : num.toCharArray()) {
            // 贪心删除：当还有删除次数且栈顶大于当前数字时，弹出栈顶
            while (k > 0 && !stack.isEmpty() && stack.peek() > digit) {
                stack.pop();
                k--;
            }
            // 将当前数字入栈
            stack.push(digit);
        }
        
        // 处理剩余的删除次数（当数字单调递增时）
        while (k > 0) {
            stack.pop();
            k--;
        }
        
        // 构建结果并处理前导零
        StringBuilder result = new StringBuilder();

        boolean leadingZero = true;
        
        // 从栈底到栈顶遍历（逆序输出）
        while (!stack.isEmpty()) {
            char digit = stack.pollLast(); // 从栈底取出元素（原顺序）
            if (leadingZero && digit == '0') {
                continue; // 跳过所有的前导零
            }
            leadingZero = false;
            result.append(digit);
        }
        
        // 返回结果，若为空则返回"0"
        return result.length() == 0 ? "0" : result.toString();

    }
}

316去除重复字母

题目

思路解析

字典序最小，这样子仍然是从左往右遍历，找出相邻的两个数

如果当前数比栈顶数小，根据条件判断是否弹出，根据不同的题进行不同的变化逻辑

该题目算是贪心算法，从左往右遍历，从遍历时候的局部最优推出全局最优

代码

import java.util.*;

class Solution {
    public String removeDuplicateLetters(String s) {

        // 统计每个字符的剩余出现次数
        Map<Character, Integer> remainCounter = new HashMap<>();
        for (char c : s.toCharArray()) {
            remainCounter.put(c, remainCounter.getOrDefault(c, 0) + 1);
        }
        
        // 使用栈来构建结果
        Deque<Character> stack = new ArrayDeque<>();

        // 记录字符是否已在栈中
        Set<Character> seen = new HashSet<>();
        
        for (char c : s.toCharArray()) {
            // 减少当前字符的剩余次数
            remainCounter.put(c, remainCounter.get(c) - 1);
            
            // 如果字符已在栈中，跳过
            if (seen.contains(c)) {
                continue;
            }
            
            // 当栈不为空，且当前字符小于栈顶字符，且栈顶字符在后续还会出现
            while (!stack.isEmpty() && c < stack.peek() && remainCounter.get(stack.peek()) > 0) {
                // 弹出栈顶字符，并从seen中移除
                seen.remove(stack.pop());
            }
            
            // 将当前字符压入栈，并标记为已处理
            stack.push(c);
            seen.add(c);
        }
        
        // 从栈底到栈顶构建结果字符串
        StringBuilder result = new StringBuilder();
        for (char c : stack) {
            result.append(c);
        }

        return result.reverse().toString();
        
    }
}

1081不同字符的最小序列

题目

1081和316题目的解法是完全相同的

思路解析

字典序最小，这样子仍然是从左往右遍历，找出相邻的两个数

如果当前数比栈顶数小，根据条件判断是否弹出，根据不同的题进行不同的变化逻辑

该题目算是贪心算法，从左往右遍历，从遍历时候的局部最优推出全局最优

代码

class Solution {
    public String smallestSubsequence(String s) {
        
        // 统计每个字符的剩余出现次数
        Map<Character, Integer> remainCounter = new HashMap<>();
        for (char c : s.toCharArray()) {
            remainCounter.put(c, remainCounter.getOrDefault(c, 0) + 1);
        }
        
        // 使用栈来构建结果
        Deque<Character> stack = new ArrayDeque<>();

        // 记录字符是否已在栈中
        Set<Character> seen = new HashSet<>();
        
        for (char c : s.toCharArray()) {
            // 减少当前字符的剩余次数
            remainCounter.put(c, remainCounter.get(c) - 1);
            
            // 如果字符已在栈中，跳过
            if (seen.contains(c)) {
                continue;
            }
            
            // 当栈不为空，且当前字符小于栈顶字符，且栈顶字符在后续还会出现
            while (!stack.isEmpty() && c < stack.peek() && remainCounter.get(stack.peek()) > 0) {
                // 弹出栈顶字符，并从seen中移除
                seen.remove(stack.pop());
            }
            
            // 将当前字符压入栈，并标记为已处理
            stack.push(c);
            seen.add(c);
        }
        
        // 从栈底到栈顶构建结果字符串
        StringBuilder result = new StringBuilder();
        for (char c : stack) {
            result.append(c);
        }

        return result.reverse().toString();
        
    }
}

321拼接最大数

题目

思路解析

一共有三个方法

pickMax（）：

从nums【】数组中找到K个最大的字典序

利用单调栈保证栈内单调递减，得到最大的且顺序的k个数组组合成的总数

merge（）：

合并两个数组，顺序生成字典序最大的组合

利用双指针，每次更新都移动i和j的位置从而实现在nums1【】和nums2【】两个数组之间的遍历

greater（）：

从指定位置开始的比较两个数组的字典序大小。从前往后依次对比，找到第一个不同的数字从而判断字典序的大小

结果取决于两个数组中第一个遇到的不同的数字

如果nums1【i】>nums2【j】返回ture

如果当 j == nums2.length ,则表示nums2 的子数组已经遍历完，但 nums1 还有剩余元素,说明nums1的字典序更大

字典序大小【1，2，3】比【1，2】大

组合逻辑解题：

暴力遍历每个可能的K个字典序

例如K=i+j

我们从nums1【】从取i个，从nums2【】中取j个，这样子i+j=k就可以组合成一个K个的最大的字典序

然后i和j不断变化

i从0->k变化

j从k ->0变化

这样子遍历2k次通过比较最终结果的字典序，拿到最大的字典序作为最终的result

代码

class Solution {
    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        int[] maxResult = new int[k];
        int m = nums1.length;
        int n = nums2.length;
        
        int start = Math.max(0, k - n);
        int end = Math.min(k, m);
        
        for (int i = start; i <= end; i++) {
            int[] sub1 = pickMax(nums1, i);
            int[] sub2 = pickMax(nums2, k - i);
            int[] result = merge(sub1, sub2);

            //比较当前组合字典序和最大字典序,从而找出最大字典序
            if (greater(result, 0, maxResult, 0)) {
                maxResult = result;
            }
        }
        
        return maxResult;
    }
    
    
    //使用 ArrayDeque 从数组中选取 k 个数字，组成最大的子序列
    //单调栈,保证栈内是单调递减的,这样子pop（）栈顶（最末尾）就能得到最大值了
    private int[] pickMax(int[] nums, int k) {
        Deque<Integer> stack = new ArrayDeque<>();
        int drop = nums.length - k; // 需要丢弃的元素数量
        
        for (int num : nums) {
            // 当还有元素可丢弃，且栈不为空，且栈顶元素小于当前元素时
            // 弹出栈顶元素（丢弃较小的元素）
            while (drop > 0 && !stack.isEmpty() && stack.peek() < num) {
                stack.pop();
                drop--;
            }
            
            // 将当前元素压入栈
            stack.push(num);
            
            //确保栈中元素最多为k个。如果超过k，则弹出栈顶元素（即最新压入的元素）
            if (stack.size() > k) {
                stack.pop();
                drop--;
            }
        }
        
        // 将栈中的元素转换为数组（注意顺序）
        int[] result = new int[k];
        for (int i = k - 1; i >= 0; i--) {
            result[i] = stack.pop();
        }
        return result;
    }
    
    
    //合并两个数组，生成字典序最大的组合
    private int[] merge(int[] nums1, int[] nums2) {

        int[] result = new int[nums1.length + nums2.length];
        int i = 0;//决定nums1的位置
        int j = 0;//决定nums2的位置
        int k = 0;//决定result的位置
        
        while (i < nums1.length || j < nums2.length) {
            if (greater(nums1, i, nums2, j)) {
                result[k++] = nums1[i++];
            } else {
                result[k++] = nums2[j++];
            }
        }
        
        return result;

    }
    

    //比较两个数组从指定位置开始的字典序大小
    private boolean greater(int[] nums1, int i, int[] nums2, int j) {
        //跳过相同的值
        while (i < nums1.length && j < nums2.length && nums1[i] == nums2[j]) {
            i++;
            j++;
        }
        //结果取决于两个数组中第一个遇到的不同的数字
        //如果nums1【i】>nums2【j】返回ture
        //如果当 j == nums2.length ,则表示nums2 的子数组已经遍历完，但 nums1 还有剩余元素,说明nums1的字典序更大
        return j == nums2.length || (i < nums1.length && nums1[i] > nums2[j]);
    }



}