Re: [閒聊] 每日leetcode
2434. Using a Robot to Print the Lexicographically Smallest String
題目 :
給你兩個字串s、t，t是一個空的字串
請遵從以下規則使s、t都變成空字串
(1) 移除s的第一個char，並將這個char加到t的最後面
(2) 移除t的最後一個char，並將這個char寫到紙上
請回傳寫在紙上按照字母序排列最小的字串
思路 :
如果i後面還有char比s[i]還小，那就只能把s[i]丟到t而不能把s[i]寫到紙上
反之如果i後面沒有char比t最後面的chat還小，那就把t最後的char寫到紙上
用一個array紀錄排在i之後最小的char
開始遍歷s，直到處理完s的最後一個char
再來把t裡面剩下的所有char寫到紙上
就可以得到答案了
C++
class Solution {
public:
string robotWithString(string s)
{
int n = s.size();
vector<char> minCharAfter(n);
string t, ans;
minCharAfter[n - 1] = s[n - 1];
for (int i = n - 2; i > -1; i--) {
if (s[i] > minCharAfter[i + 1]) {
minCharAfter[i] = minCharAfter[i + 1];
} else {
minCharAfter[i] = s[i];
}
}
for (int i = 0; (i < n || t.size() > 0);) {
if (t.size() > 0 && (i == n || t.back() <= minCharAfter[i])) {
char c = t.back();
t.pop_back();
ans.push_back(c);
} else {
t.push_back(s[i]);
i++;
}
}
return ans;
}
};
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 203.121.235.241 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1749221326.A.53A.html
討論串 (同標題文章)
完整討論串 (本文為第 1443 之 1548 篇)：