社区 › 业界 › hot100之贪心

袁可佳 发表于 2025-9-24 15:27:35

hot100之贪心

买卖股票的最佳时期(121)

class Solution {
    public int maxProfit(int[] prices) {
      int res = 0;
      int min = Integer.MAX_VALUE;

      for (int i = 0; i < prices.length; i++){
            min = Math.min(min, prices);
            res = Math.max(res,prices - min);
      }
      return res;
    }
}

[*]感悟
贪心就是贪局部最优解, 扩散到全局
跳跃游戏(055)

class Solution {
    public boolean canJump(int[] nums) {
      int max_length = 0;
      int i = 0;
      for (; max_length >= i && i < nums.length; i++){
            max_length = Math.max(max_length, i + nums);
      }
      return i == nums.length;
    }
}

[*]分析
max_length来维护理论可达距离
跳跃游戏II(045)

class Solution {
    public int jump(int[] nums) {
      int n = nums.length;
      int res = 0;
      int curr = 0;
      int nextCurr = 0;
      for (int i = 0; i < n-1 ; i++){
            nextCurr = Math.max(nextCurr, i+ nums);
            if (i == curr){
                curr = nextCurr;
                res++;
            }
      }
      return res;
    }
}

[*]分析
curr 维护本次跳跃最大可达距离
nextCurr 通过遍历途经点, 维护下次跳跃最大可达距离
划分字母区间(763)

class Solution {
    public List<Integer> partitionLabels(String s) {
      int n = s.length();
      char[] charArray = s.toCharArray();
      int[] last = new int;
      for (int i = 0 ; i < n; i++){
            last- 'a'] = i;
      }

      List<Integer> res = new ArrayList<>();
      int start = 0;
      int end = 0;
      for (int i = 0; i < n; i++){
            end = Math.max(end, last - 'a']);
            if (end == i){
                res.add(end - start + 1);
                start = i+1;
            }
      }
      return res;
    }
}

[*]分析
将字符串预处理, 产生每个字符的最大索引
提取范围内字符的最远索引来更新end

[*]感悟
遇到这种熟悉又陌生的题型真别怕, 先把陌生数据转换成熟悉的, 这题就跟跳跃游戏II(045)一样了

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

查看完整版本: hot100之贪心