LeetCode - Array - Easy - 121

    xiaoxiao2022-06-24  179

    思路:时间复杂度O(n),从前向后遍历,找到最小的buyPro的同时,计算maxPro 举例:[7,1,5,3,6,4]

    i012345buyPro711111maxPro004455 class Solution { public: int maxProfit(vector<int>& prices) { int maxPro=0,numPro=prices.size(); if(numPro==0){ return 0; } int buyPro=prices[0]; for(int i=1;i<numPro;i++){ if(prices[i]>buyPro){ maxPro=max(maxPro,prices[i]-buyPro); }else{ buyPro=prices[i]; } } return maxPro; } };

    时间复杂度:O(n) 空间复杂度:O(1)


    最新回复(0)