LeetCode 1081. 不同字符的最小子序列

Categories:

题目描述
思路分析
1. 解法一：单调栈（推荐）
相似题目

题目描述

✅ 1081. 不同字符的最小子序列

思路分析

解法一：单调栈（推荐）

核心思路：

统计每个字符的最后出现位置。

维护一个递增栈，保证字典序最小且字符唯一。

当前字符比栈顶小且栈顶字符后面还能出现时，弹栈。

复杂度分析：

时间复杂度：O(n)，其中 n 表示字符串长度。

空间复杂度：O(n)，用于栈与访问标记。

class Solution {
    public String smallestSubsequence(String s) {
        int[] last = new int[26];
        for (int i = 0; i < s.length(); i++) {
            last[s.charAt(i) - 'a'] = i;
        }

        boolean[] used = new boolean[26];
        StringBuilder stack = new StringBuilder();

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            int idx = c - 'a';

            if (used[idx]) {
                continue;
            }

            while (stack.length() > 0) {
                char top = stack.charAt(stack.length() - 1);
                if (top > c && last[top - 'a'] > i) {
                    used[top - 'a'] = false;
                    stack.deleteCharAt(stack.length() - 1);
                } else {
                    break;
                }
            }

            stack.append(c);
            used[idx] = true;
        }

        return stack.toString();
    }
}

func smallestSubsequence(s string) string {
	last := make([]int, 26)
	for i := 0; i < len(s); i++ {
		last[s[i]-'a'] = i
	}

	used := make([]bool, 26)
	stack := make([]byte, 0)

	for i := 0; i < len(s); i++ {
		c := s[i]
		idx := c - 'a'
		if used[idx] {
			continue
		}

		for len(stack) > 0 {
			top := stack[len(stack)-1]
			if top > c && last[top-'a'] > i {
				used[top-'a'] = false
				stack = stack[:len(stack)-1]
			} else {
				break
			}
		}

		stack = append(stack, c)
		used[idx] = true
	}

	return string(stack)
}

相似题目

题目	难度	考察点
316. 去除重复字母	中等	单调栈
1081. 不同字符的最小子序列	中等	单调栈
402. 移掉K位数字	中等	单调栈
1673. 找出最具竞争力的子序列	中等	单调栈
1081. 不同字符的最小子序列	中等	单调栈

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/58180207