文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

描述

給定一個字符串str，現在要對該字符串進行刪除操作，
保留字符串中的 k 個字符且相對位置不變，并且使它的字典序最小，返回這個子串。

示例

例1: 輸入:str="fskacsbi",k=2 輸出:"ab" 解釋:“ab“是str中長度為2并且字典序最小的子串例2: 輸入:str="fsakbacsi",k=3 輸出:"aac"

來源：https://tianchi.aliyun.com/oj/141758389886413149/160295184768372893

2. 解題

class Solution { public:/*** @param str: the string* @param k: the length* @return: the substring with the smallest lexicographic order*/string deleteChar(string &str, int k) {// Write your code here.int n = str.size();if(k >= n)//不用刪return str;int del = n-k;//要刪除的個數stack<char> stk;for(int i = 0; i < n; i++){while(!stk.empty() && stk.top() > str[i] && del){ //還可刪del > 0 且 前面的字符比當前的大，刪除之stk.pop();del--;}stk.push(str[i]);}while(del--)//還沒刪完的，從尾巴開始刪stk.pop();string ans;while(!stk.empty()){ans = stk.top() + ans;stk.pop();}return ans;} };

50ms C++

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的天池 在线编程 删除字符（单调栈）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。