LeetCode2012

LeetCode2012

目录

• 题目描述
• 示例
• 思路分析
• 代码段
• 代码逐行讲解
• 复杂度分析
• 总结的知识点
• 整合
• 总结

题目描述

给定一个整数数组 nums，定义数组的 美丽值 为满足以下条件的元素个数：

1. 如果一个元素大于其左边所有元素且小于其右边所有元素，则其美丽值为 2。
2. 如果一个元素大于其左边元素且小于其右边元素，则其美丽值为 1。
3. 否则，其美丽值为 0。

请你返回数组 nums 的美丽值之和。

示例

示例 1

输入:

nums = [1, 2, 3]

输出:

2

解释:

• 元素 2 的美丽值为 2。
• 元素 3 的美丽值为 0。
• 美丽值之和为 2。

示例 2

输入:

nums = [2, 4, 6, 4]

输出:

1

解释:

• 元素 4 的美丽值为 1。
• 美丽值之和为 1。

示例 3

输入:

nums = [3, 2, 1]

输出:

0

解释:

• 没有元素的美丽值大于 0。

思路分析

问题核心

我们需要计算数组中每个元素的美丽值，并返回美丽值之和。

思路拆解

1. 初始化变量：
   • 使用数组 dp 记录每个元素是否大于其左边所有元素。
   • 使用变量 max 记录当前元素左边的最大值。
2. 遍历数组：
   • 从左到右遍历数组，更新 dp 数组和 max。
3. 计算美丽值：
   • 从右到左遍历数组，计算每个元素的美丽值，并累加到结果中。

代码段

class Solution {
    public int sumOfBeauties(int[] nums) {
        int len = nums.length;
        int ans = 0;
        int[] dp = new int[len];
        int max = nums[0], min = nums[len - 1];
        for (int i = 1; i <= len - 2; i++) {
            if (nums[i] > max) {
                dp[i] = 1;
                max = nums[i];
            }
        }
        for (int i = len - 2; i >= 1; i--) {
            if (dp[i] == 1 && nums[i] < min) {
                ans += 2;
            } else if (nums[i - 1] < nums[i] && nums[i] < nums[i + 1]) {
                ans += 1;
            }
            min = Math.min(min, nums[i]);
        }
        return ans;
    }
}

代码逐行讲解

1. 初始化变量：

   int len = nums.length;
   int ans = 0;
   int[] dp = new int[len];
   int max = nums[0], min = nums[len - 1];
   

   • 获取数组长度，并初始化结果变量 ans、辅助数组 dp 和最大值 max、最小值 min。

2. 从左到右遍历数组：

   for (int i = 1; i <= len - 2; i++) {
       if (nums[i] > max) {
           dp[i] = 1;
           max = nums[i];
       }
   }
   

   • 遍历数组，更新 dp 数组和 max。

3. 从右到左遍历数组：

   for (int i = len - 2; i >= 1; i--) {
       if (dp[i] == 1 && nums[i] < min) {
           ans += 2;
       } else if (nums[i - 1] < nums[i] && nums[i] < nums[i + 1]) {
           ans += 1;
       }
       min = Math.min(min, nums[i]);
   }
   

   • 遍历数组，计算每个元素的美丽值，并累加到结果中。

4. 返回结果：

   return ans;
   

   • 返回美丽值之和。

复杂度分析

时间复杂度

• 遍历数组两次，时间复杂度为 O(n)。

空间复杂度

• 使用了辅助数组 dp，空间复杂度为 O(n)。

总结的知识点

1. 数组遍历：

   • 通过遍历数组更新最大值和最小值。

2. 条件判断：

   • 根据条件判断计算每个元素的美丽值。

3. 辅助数组：

   • 使用辅助数组记录中间结果。

整合

class Solution {
    public int sumOfBeauties(int[] nums) {
        int len = nums.length;
        int ans = 0;
        int[] dp = new int[len];
        int max = nums[0], min = nums[len - 1];
        for (int i = 1; i <= len - 2; i++) {
            if (nums[i] > max) {
                dp[i] = 1;
                max = nums[i];
            }
        }
        for (int i = len - 2; i >= 1; i--) {
            if (dp[i] == 1 && nums[i] < min) {
                ans += 2;
            } else if (nums[i - 1] < nums[i] && nums[i] < nums[i + 1]) {
                ans += 1;
            }
            min = Math.min(min, nums[i]);
        }
        return ans;
    }
}

总结

通过遍历和条件判断，能够高效地计算数组中每个元素的美丽值，并返回美丽值之和。