408算法题leetcode--第二天

1281. 整数的各位积和之差

• 1281. 整数的各位积和之差\
• 思路：模拟，用取余获取每一位数
• 时间复杂度：O(n的位数) = O(logn)，空间复杂度：O(1)

class Solution {
public:int subtractProductAndSum(int n) {int mul = 1, sum = 0;while(n){int temp = n % 10;mul *= temp;sum += temp;n /= 10;}return mul - sum;}
};

1822. 数组元素积的符号

• 1822. 数组元素积的符号
• 思路：遍历数组即可
• 时间复杂度：O(N)，空间：O(1)

class Solution {
public:int arraySign(vector<int>& nums) {int ret = 1;for(auto i : nums){if(i == 0){return 0;}if(i < 0) ret *= -1;}return ret;}
};

896. 单调数列

• 896. 单调数列
• 思路：用两个临时变量，遍历数组，分别判断是否递增或递减
• 时间复杂度：O(n)，空间：O(1)

class Solution {
public:bool isMonotonic(vector<int>& nums) {int inc = 1, dec = 1;int size = nums.size();for(int i = 0; i < size - 1; i++){if(nums[i + 1] < nums[i]){  // 判断是否递增inc = 0;}if(nums[i + 1] > nums[i]){  // 判断是否递减dec = 0;}}return inc || dec;}
};

121. 买卖股票的最佳时机

• 121. 买卖股票的最佳时机
• 思路：遍历数组，记录此时的最小成本以及最大利润
• 时间复杂度：O()，空间：O()

class Solution {
public:int maxProfit(vector<int>& prices) {int min_price = 1e9, max_profit = 0;for(auto i : prices){max_profit = max(max_profit, i - min_price);min_price = min(min_price, i);}return max_profit;}
};