在做字节跳动周赛时候看到一个很有趣的题解,原来双指针不一定是得用在排序的数组里头 https://leetcode-cn.com/problems/maximum-difference-between-increasing-elements/
解法一:栈 我们从后面开始遍历数组,先把最后一个入栈,当发现一个元素比栈顶的大说明这个元素可以取代栈顶,进栈,当一个元素比之小,可以把他拿进去和ans比较代码如下O(n):
class Solution {
public:
stack<int>record;
int maximumDifference(vector<int>& nums) {
if(nums.size()==1) return -1;
int ans=-100;
record.push(nums[nums.size()-1]);
for(int i=nums.size()-2;i>=0;i--){
if(!record.empty()){
if(record.top()>nums[i]){
ans=max(ans,record.top()-nums[i]);
}else{
record.push(nums[i]);
}
}
}
return ans==-100? -1:ans;
}
};
解法二: 我们维护两个指针当右指针的元素比左的大时,不断的移动右指针,如果小说明找到了比当前的左指针指向的元素还要小的一个元素,更新这个最小的元素作为新的num[left] 因为这样在后面找元素num[right] (比num[left]大的)时候可以减去一个更小的 使得答案最大 双指针 好像有点贪心的味道在这里了…
class Solution {
public int maximumDifference(int[] nums) {
int left=0;
int right=1;
int max=-1;
while(right<nums.length){
if(nums[left]<nums[right]){
max = Math.max(max,nums[right]-nums[left]);
}else{
left=right;
}
right++;
}
return max;
}
}
|