貪心算法的詳細邏輯
這個問題的最優解可以用?貪心算法?在?O(N) 時間?內解決。它的核心思想是：
每次操作盡可能覆蓋最長的連續非零區間，并通過數學分析發現：最小操作次數等于所有“上升臺階”的高度差之和。
1. 直觀理解
假設?steps = [1, 2, 3, 2, 1]，我們可以這樣操作：
第一次操作：覆蓋整個數組?
[1,2,3,2,1]?→?[0,1,2,1,0]
（操作次數 +=1）第二次操作：覆蓋?
[1,2,1]?→?[0,0,1,0,0]
（操作次數 +=1）第三次操作：覆蓋?
[1]?→?[0,0,0,0,0]
（操作次數 +=1）
總操作次數 = 3，正好等于?1 (初始) + (2-1) + (3-2) = 3。
2. 貪心策略的數學證明
關鍵觀察：
如果當前數字?
steps[i]?比前一個數字?steps[i-1]?大，說明需要?新增?steps[i] - steps[i-1]?次操作。如果?
steps[i] <= steps[i-1]，說明它可以被之前的操作覆蓋，無需新增操作次數。
數學表達：
text
總操作次數 = steps[0] + Σ max(steps[i] - steps[i-1], 0) (i = 1 to N-1)
3. 代碼實現
cpp
#include <vector>
#include <iostream>
using namespace std;int GetMinStep(const vector<int>& steps) {if (steps.empty()) return 0;int res = steps[0]; // 初始必須有 steps[0] 次操作for (int i = 1; i < steps.size(); i++) {if (steps[i] > steps[i-1]) {res += steps[i] - steps[i-1]; // 增加新的操作}}return res;
}int main() {vector<int> steps1 = {1, 2, 3, 2, 1};cout << GetMinStep(steps1) << endl; // 輸出 3vector<int> steps2 = {3, 2, 1, 2, 3};cout << GetMinStep(steps2) << endl; // 輸出 5vector<int> steps3 = {4, 1, 2, 3, 1};cout << GetMinStep(steps3) << endl; // 輸出 6 (4 + 0 + 1 + 1 + 0)return 0;
}4. 為什么貪心算法是正確的？
反證法
假設貪心算法不是最優的，那么存在某個?steps[i]?沒有被正確覆蓋：
情況 1：
steps[i] > steps[i-1]
如果少操作，會導致?steps[i]?無法歸零，矛盾。情況 2：
steps[i] <= steps[i-1]
它已經被之前的操作覆蓋，無需額外操作。
因此，貪心策略的正確性得證。
5. 對比原始模擬方法
| 方法 | 時間復雜度 | 適用場景 |
|---|---|---|
| 原始模擬（每次找最長區間減1） | O(N2) | 直觀但較慢 |
| 貪心算法（數學優化） | O(N) | 最優解 |
6. 實際應用示例
示例 1：steps = [3, 2, 1, 2, 3]
計算過程：
res = 3（初始）i=1:?2 <= 3?→ 不增加i=2:?1 <= 2?→ 不增加i=3:?2 > 1?→?res += 1?→?res=4i=4:?3 > 2?→?res += 1?→?res=5
總操作次數 = 5
示例 2：steps = [4, 1, 2, 3, 1]
計算過程：
res = 4（初始）i=1:?1 <= 4?→ 不增加i=2:?2 > 1?→?res += 1?→?res=5i=3:?3 > 2?→?res += 1?→?res=6i=4:?1 <= 3?→ 不增加
總操作次數 = 6
7. 總結
貪心策略：利用高度差直接計算最小操作次數。
優勢：O(N) 時間，無需模擬每次操作。
適用場景：題目允許數學分析時，優先使用貪心算法。
這種方法高效且優雅，能完美解決問題！ 🎯
資源?
#include <iostream>
#include <vector>
#include <climits>
#include <queue>
#include <list>
#include <unordered_set>
using namespace std;
void PrintList(list<pair<int,int>> lists)
{for(auto l:lists){cout<<"<"<<l.first<<" "<<l.second<<">"<<" ";}cout<<endl;
}int Solution(const int frameNum, const int windowSize, const vector<int> pages)
{int ret = 0;// 記錄訪問次數，訪問時間，// <51 1> <52 1> <53 1>// <52 1> <53 1> <54 1>// 要么遍歷一遍時間，要么遍歷一遍page，要么加空間// 鏈表比較合適，list<pair<int,int>> pagesList;for(auto& page:pages){auto it = pagesList.begin();bool flagFind = false;while(it!=pagesList.end()){if(it->first == page){flagFind = true;it->second++;break;}it++;}if(flagFind == false){if(pagesList.size()<frameNum){pagesList.push_back(make_pair(page,1));}else // 觸發置換{//從頭節點開始取windowSize個//遍歷得到最小值auto left = pagesList.begin();int nums = windowSize;int minof = INT_MAX;while (nums>0){minof = min(minof,left->second);left++;nums--;}nums = windowSize;left = pagesList.begin();while (nums>0){if(left->second==minof){pagesList.erase(left);pagesList.push_back(make_pair(page,1));break;}left++;nums--;}ret++;}}//PrintList(pagesList);//cout<<ret<<endl;}return ret;
}單詞統計
int Solution(const vector<string> lines)
{// 需要特殊處理的 " " . , -string allLines;int ret = 0;for(int l=0;l<lines.size();l++){int i =0;if(lines[l] == "-"){ } else{ while (i<lines[l].size()){while(i<lines[l].size()&&(lines[l][i]==','||lines[l][i]=='.'||lines[l][i]==' ')){i++;}if(i<lines[l].size()){ret++;while((i<lines[l].size())&&(lines[l][i]<='z'&&lines[l][i]>='a')){i++;} }if((i==lines[l].size()-1 )&& lines[l][i]=='-') {i++;if(l+1<lines.size()&&lines[l+1][0]>='a'&&lines[l+1][0]<='z') { ret--;}if(l+1<lines.size()&&lines[l+1]=="-"){ret--;}}}}}return ret;
}
