五月集训-01【数组】

• 前言
• 一、练习题目
• 二、思路及题解
• • 1. LC2016-增量元素之间的最大差值
  • 2. LC2239-找到最接近 0 的数字
  • 3. LC1475-商品折扣后的最终价格
  • 4. LC2248-多个数组求交集
• 总结

        欢迎大家积极在评论区留言一起讨论交流，知无不言，言无不尽，共同进步。本文是 数组 专题，更多其他专题内容详见《LeetCode每月集训系列》

方法一：前缀最小值

（1）对于每个数对中的 nums[j] 而言，对应的 nums[i] 必然是下标 j 左侧的最小值;
（2）如果 nums[j] > premin ，那么就用 nums[j] − premin 对答案进行更新；
（3）否则，用 nums[j] 来更新前缀最小值 。

代码如下：

class Solution {
public:
    int maximumDifference(vector& nums) {
        int n = nums.size();
        int ans = -1, premin = nums[0];
        for (int i = 1; i < n; ++i) {
            if (nums[i] > premin) {
                ans = max(ans, nums[i] - premin);
            } else {
                premin = nums[i];
            }
        }
        return ans;
    }
};

方法一：遍历

（1）通过遍历得到元素中绝对值最小，且数值最大的元素。首先定义一个 num 来储存最小绝对值，ans 用来储存数值最大的元素；
（2）当∣nums[i]∣ < num 时，需要将 num 更新为 |nums[i]| ，并将 ans 更新为 nums[i]；
（3）当 ∣num∣ = num 时，需要将 ans 更新为 ans 与 nums[i] 的最大值。

代码如下：

class Solution {
public:
    int findClosestNumber(vector& nums) {
        int n = nums.size();
        int num = abs(nums[0]);  // 存储最小绝对值
        int ans = nums[0];  // 存储数值最大元素
        for (int i = 1; i < n; i++) {
            if (num > abs(nums[i])) {
                num = abs(nums[i]);
                ans = nums[i];
            } else if (num == abs(nums[i])) {
                ans = nums[i] > ans ? nums[i] : ans;
            }
        }
        return ans;
    }
};

方法一：常规操作

（1）暴力双循环，无需多言，懂得都懂。

代码如下：

class Solution {
public:
    vector finalPrices(vector& prices) {
        for (int i = 0; i < prices.size(); ++i) {
            for (int j = i + 1; j < prices.size(); ++j) {
                if (prices[j] <= prices[i]) {
                    prices[i] -= prices[j];
                    break;
                }
            }
        }
        return prices;
    }
};

方法二：单调递增栈

（1）如果想要获得折扣，则必须获取后方一个小于等于该元素的值。

代码如下：

class Solution {
public:
    vector finalPrices(vector& prices) {
        stack stk;
        vector result = prices;
        for (int i = 0; i < prices.size(); ++i) {
            while (!stk.empty() && prices[i] <= prices[stk.top()]) {
                result[stk.top()] = prices[stk.top()] - prices[i];
                stk.pop();
            }
            stk.push(i);
        }
        return result;
    }
};

方法一：哈希表

（1）由于每个数组中的元素互不相同，即可通过哈希表统计在每个数组中出现的次数；
（2）如果一个元素在每个数组中均出现过，则它在 nums 中的出现次数应等于 n ；
（3）最后遍历哈希表找出值为 n 的元素，然后返回经排序后数组即可。

代码如下：

class Solution {
public:
    vector intersection(vector>& nums) {
        vector res;
        map map;  // 有序 -> 最后返回的结果也是有序的，无需再次调整
        for (vector& num : nums) {
            for (int x :num) {
                ++map[x];  // 记录每个值出现次数
            }
        }
        for (pair iter : map) {
            if (iter.second == nums.size()) {
                res.push_back(iter.first);  // 若在每个数组中都出现过则为数组的交集
            }
        }
        return res;
    }
};

        题目难不要怕，只要每个月的每一天都坚持刷题学习，总有一天会熟练掌握的。欢迎加入【知识星球｜英雄算法联盟】与我们一同早起刷刷刷⛽️