华为OD机试 - 最多购买宝石数目 - 滑动窗口（Java 2024 C卷 100分）

深碍√TFBOYSˉ_ 2024-05-01 16:27 82阅读 0赞

![在这里插入图片描述][986dcebce006483fb6846cb29a3928a7.gif_pic_center]

> 华为OD机试 2024C卷题库疯狂收录中，刷题[**点这里**][Link 1]

### 专栏导读 ###

本专栏收录于[《华为OD机试（JAVA）真题（A卷+B卷+C卷）》][OD_JAVA_A_B_C]。

**刷的越多，抽中的概率越大**，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。

### 一、题目描述 ###

橱窗里有一排宝石，不同的宝石对应不同的价格，宝石的价格标记为 gems\[i\],0<=i<n, n = gems.length

宝石可同时出售0个或多个，如果同时出售多个，则要求出售的宝石编号连续；

例如客户最大购买宝石个数为m，购买的宝石编号必须为gems\[i\],gems\[i+1\]…gemsi+m-1

假设你当前拥有总面值为value的钱，请问最多能购买到多少个宝石,如无法购买宝石，则返回 0。

### 二、输入描述 ###

第一行输入n，参数类型为int，取值范围：\[0,10^6\]，表示橱窗中宝石的总数量。

之后n行分别表示从第0个到第n-1个宝石的价格，即gems\[0\]到gems\[n-1\]的价格，类型为int，取值范围：(0,1000\]。

之后一行输入v，类型为int，取值范围：\[0,10^9\]表示你拥有的钱。

### 三、输出描述 ###

输出int类型的返回值，表示最大可购买的宝石数量。

#### 1、输入 ####

7  
8  
4  
6  
3  
1  
6  
7  
10

#### 2、输出 ####

### 四、解题思路 ###

1.  使用两个指针 left 和 right 来表示滑动窗口的左右边界，初始化它们都为0。
2.  不断尝试扩展右边界 right，直到我们无法再购买更多宝石或者超出了我们的预算。
3.  在每次尝试扩展右边界的过程中，我们记录当前窗口内的宝石数量，并更新最大宝石数量。
4.  如果当前窗口内的宝石总价值超过了我们的预算，我们就需要缩小窗口，即增加左边界 left，直到窗口内的宝石总价值不再超过预算或左边界 left 达到了 n - m，这是因为在这种情况下即使窗口再向右扩展也无法满足连续购买的条件。
5.  最后，返回记录的最大宝石数量即可。

### 五、Java算法源码 ###

public class OdTest02 {
        
        public static void main(String[] args) {
        
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt(); // 宝石的总数量
            int[] gems = new int[n];
            for (int i = 0; i < n; i++) {
        
                gems[i] = sc.nextInt(); // 宝石的价格
            }
            int v = sc.nextInt(); // 拥有的钱
    
            int left = 0; // 滑动窗口左边界
            int right = 0; // 滑动窗口右边界
            int maxGems = 0; // 最大可购买宝石数量
            int sum = 0; // 当前窗口内宝石总价值
    
            // 开始滑动窗口
            while (right < n) {
        
                sum += gems[right]; // 尝试扩展右边界，并更新窗口内宝石总价值
                right++;
    
                // 如果当前窗口内宝石总价值超过了预算，缩小窗口
                while (sum > v && left < n) {
        
                    sum -= gems[left]; // 缩小窗口，更新宝石总价值
                    left++;
                }
    
                // 更新最大可购买宝石数量
                maxGems = Math.max(maxGems, right - left);
            }
            System.out.println(maxGems);
        }
    }

### 六、效果展示 ###

#### 1、输入 ####

9  
6  
1  
3  
1  
8  
9  
3  
2  
4  
15

#### 2、输出 ####

#### 3、说明 ####

![在这里插入图片描述][aaa2bdbb4c4f4af9b004fea6f7535e34.png_pic_center]

?下一篇：[华为OD机试 - 简易内存池 - 逻辑分析（Java 2024 C卷 200分）][OD_ - _ - _Java 2024 C_ 200]

?本文收录于，[华为OD机试（JAVA）真题（A卷+B卷+C卷）][OD_JAVA_A_B_C]

**刷的越多，抽中的概率越大**，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。

![在这里插入图片描述][8dbe8dd8723c4636af5926ccf1c511b0.gif_pic_center]

[986dcebce006483fb6846cb29a3928a7.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/01/7b1c5565792a4f4f95222faef74b1c42.gif
[Link 1]: https://blog.csdn.net/guorui_java/article/details/132683473
[OD_JAVA_A_B_C]: https://blog.csdn.net/guorui_java/category_12293298.html
[aaa2bdbb4c4f4af9b004fea6f7535e34.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/01/1ebf86be68184dc9984e745929389687.png
[OD_ - _ - _Java 2024 C_ 200]: https://blog.csdn.net/guorui_java/article/details/132197477
[8dbe8dd8723c4636af5926ccf1c511b0.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/01/2d84355ccd5d400e80c91f7ac467c9e8.gif