前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【Leetcode-1574.删除最短的子数组使剩余数组有序(C语言)】

【Leetcode-1574.删除最短的子数组使剩余数组有序(C语言)】

作者头像
YoungMLet
发布2024-03-01 09:12:00
1000
发布2024-03-01 09:12:00
举报
文章被收录于专栏:C++/Linux
Leetcode-1574.删除最短的子数组使剩余数组有序

Leetcode-1574.

题目:给你一个整数数组 arr ,请你删除一个子数组(可以为空),使得 arr 中剩下的元素是非递减的。一个子数组指的是原数组中连续的一个子序列。请你返回满足题目要求的最短子数组的长度。

首先我们的思路是双指针,一个从头部开始,一个从尾部开始; 尾部的先往前找,找到开始递增的临界点记录下来;然后再依次与头部的指针相对比;

下面我们直接看代码以及注释:

代码语言:javascript
复制
			int findLengthOfShortestSubarray(int* arr, int arrSize) 
			{
			    int j = arrSize - 1;
			    //j从尾部开始往前找(尾部往前是递减的),找到开始递增的的临界点的下标j
			    //注意这里j>0要放在arr[j - 1] <= arr[j]的前面,不然Leetcode过不了
			    while (j > 0 && arr[j - 1] <= arr[j])
			    {
			        j--;
			    }
			    if (j == 0)
			    {
			        return 0;
			    }
			    //将j的下标赋给len,现在代表从下标0开始到j相差的长度为len
			    int len = j;
			    //j从len的位置开始
			    //i从前面开始往后走(从前往后走是递增的),i每走一步,更新len的长度j-i-1;
			    //因为len会记录i上一次所在元素时与j相差的长度,理论上arr[i] <= arr[j] ,满足这个条件时有可能记录的这个长度就是题目所求,
			    //但是为了求最优解,i还需要往后走,当 arr[i] > arr[j] 时j也往后走,直到满足arr[i] <= arr[j],继续记录这时的长度;
			    for (int i = 0; i < arrSize; i++)
			    {
			        while (j < arrSize && arr[i] > arr[j])
			        {
			            j++;
			        }
			        //更新长度
			        if ((j - i - 1) < len)
			        {
			            len = j - i - 1;
			        }
			        //在记录长度的同时,也要保证arr[i] > arr[i + 1]并且数组不越界,如果不满足条件,直接跳出循环,返回的这个len值就是最优解
			        if (arr[i] > arr[i + 1] && i + 1 < arrSize)
			        {
			            break;
			        }
			    }
			    return len;
			}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2023-03-31,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • Leetcode-1574.删除最短的子数组使剩余数组有序
  • Leetcode-1574.
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档