連結
Maximum Difference Between Increasing Elements
想法
一開始會想到的是暴力解，直接雙迴圈來計算
|
1 2 3 4 5 6 7 8 9 10 11 12 |
class Solution { public: int maximumDifference(vector<int>& nums) { int maxVal = INT_MIN; for(int i=0; i < (int) nums.size(); ++i){ for(int j=i+1; j < (int) nums.size(); ++j){ maxVal = max(maxVal, nums[j]-nums[i]); } } return (maxVal <= 0)? -1 : maxVal ; } }; |
接下來是優化的方式，這題的重點其實就是找目前 i 位置右變最大值的數，舉例來說
|
1 2 3 4 5 6 7 |
假設 Array 是 [1,2,5,4,8]，目前 i = 0 i [1,2,5,4,8] i 右邊有 2,5,4,8，題目希望 2 數相差越大越好 所以就是找 2,5,4,8 中的最大值 8，這樣 8-1 = 7 相差最大 |
那上述暴力解使用的迴圈是由左往右遍歷，所以一定無法得知右邊最大值是多少
這時就需要由右往左迴圈，遍歷過程中持續記錄最大值
|
1 2 3 4 5 6 7 8 9 10 11 12 |
// 第一步，先寫好由右往左的迴圈，同時記錄 i 的右邊最大值 class Solution { public: int maximumDifference(vector<int>& nums) { // 初始化最右邊為最大值 int maxVal = nums.back(); for(int i=nums.size()-2; i >=0; --i){ maxVal = max(maxVal, nums[i]); } return 0; } }; |
接下來就是加入題目要的條件，計算 num[i] 和右邊最大值相差多少且nums[i] < 右邊最大值
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
class Solution { public: int maximumDifference(vector<int>& nums) { int maxVal = nums.back(); int ans = 0; for(int i=nums.size()-2; i >=0; --i){ // ================================== // 第二步，只要符合條件 "nums[i] < 右邊最大值"，就把相差多少紀錄起來 if( nums[i] < maxVal ){ ans = max(ans, maxVal-nums[i]); } // ================================== maxVal = max(maxVal, nums[i]); } return (ans <= 0 ) ? -1 : ans; } }; |
