สมมติว่าเรามีสตริงตัวอักษรพิมพ์เล็กและมีรายการค่าใช้จ่ายที่เป็นค่าไม่ติดลบ เรียกว่า costs สตริงและรายการมีความยาวเท่ากัน เราสามารถลบตัวอักษร s[i] ด้วยค่าใช้จ่าย costs[i] และทั้ง s[i] และ costs[i] จะถูกลบออก เราต้องหาต้นทุนขั้นต่ำในการลบตัวอักษรที่ซ้ำติดกันทั้งหมด
เช่น ถ้าอินพุตเป็น s = "xxyyx" nums = [2, 3, 10, 4, 6] ผลลัพธ์จะเป็น 6 เพราะเราสามารถลบ s[0] และ s[3] ด้วยค่าใช้จ่ายรวม 2 + 4 = 6
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนต่อไปนี้:
กำหนดสแต็ก st
cost := 0
ลูป i จาก 0 ถึงขนาดของ s - 1:
ถ้าขนาดของ st ไม่ใช่ 0 และ s[top ของ st] เท่ากับ s[i] ให้:
ถ้า nums[top ของ st] > nums[i] ให้:
cost := cost + nums[i]
มิฉะนั้น:
cost := cost + nums[top ของ st]
pop องค์ประกอบออกจาก st
push i เข้า st
มิฉะนั้น ให้ push i เข้า st
คืนค่า cost
ตัวอย่าง
#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
