當前位置:成語大全網 - 新華字典 - LeetCode-python 316.去除重復字母

LeetCode-python 316.去除重復字母

題目鏈接

難度:困難 ?類型: 貪心、棧

給定壹個僅包含小寫字母的字符串,去除字符串中重復的字母,使得每個字母只出現壹次。需保證返回結果的字典序最小(要求不能打亂其他字符的相對位置)。

示例1

示例2

遍歷數組,壹個壹個考慮是否需要,若需要,就存入stack

遍歷之前用collections.Counter統計每個字母的個數

當遍歷到第i個字母s[i]時,首先s[i]的總個數減去1,再考慮這個字母要不要加入stack,加入之前,還要看已經加入的字母需不需要從stack中刪除,例如bab,第壹個b是要被刪除的,因為b的字典序大於a,且a之後還有壹個b,所以可以保留後壹個b而刪掉前壹個b。那麽,刪除stack中最後壹個字母stack[-1]的條件就是:

stack不空 且 stack[-1] > s[i] 且 s[i]不在stack中 且 stack[-1]的個數大於零

s[i]加入stack的條件就是:

s[i]不在stack中

本文鏈接: /p/e31aed2b4dc5