สมมติว่าเรามีสตริงที่มีตัวพิมพ์เล็กและเรายังมีรายการค่าที่ไม่ใช่ค่าลบที่เรียกว่าค่าใช้จ่าย สตริงและรายการมีความยาวเท่ากัน เราสามารถลบอักขระ s[i] สำหรับ costcost[i] จากนั้นทั้ง s[i] และ cost[i] จะถูกลบออก เราต้องหาต้นทุนขั้นต่ำเพื่อลบอักขระที่ซ้ำกันทั้งหมดทั้งหมด
ดังนั้น หากอินพุตเป็น s ="xxyyx" nums =[2, 3, 10, 4, 6] ผลลัพธ์จะเป็น 6 ในขณะที่เราลบ s[0] และ s[3] สำหรับค่าใช้จ่ายทั้งหมด 2 + 4 =6.
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้
-
กำหนดหนึ่งสแต็ก st
-
ราคา :=0
-
สำหรับการเริ่มต้น i :=0 เมื่อ i
-
ถ้าขนาดของ st ไม่ใช่ 0 และ s[top of st] เท่ากับ s[i] ดังนั้น:
-
ถ้า nums[top of st]> nums[i] แล้ว:
-
ราคา :=ราคา + จำนวน[i]
-
-
อย่างอื่น:
-
cost :=cost + nums[top of st]
-
องค์ประกอบป๊อปจาก st
-
ดันฉันเข้า st
-
-
-
อย่างอื่น
-
ดันฉันเข้า st
-
-
-
ค่าส่งคืน
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int solve(string s, vector<int>& nums) {
stack<int> st;
int cost = 0;
for (int i = 0; i < s.size(); ++i) {
if (st.size() && s[st.top()] == s[i]) {
if (nums[st.top()] > nums[i]) {
cost += nums[i];
} else {
cost += nums[st.top()];
st.pop();
st.push(i);
}
} else {
st.push(i);
}
}
return cost;
}
};
int solve(string s, vector<int>& nums) {
return (new Solution())->solve(s, nums);
}
main(){
vector<int> v = {2, 3, 10, 4, 6};
string s = "xxyyx";
cout << solve(s, v);
} อินพุต
"xxyyx",{2,3,10,4,6} ผลลัพธ์
6
