首页 > 试题广场 >

排序子序列

[编程题]排序子序列

热度指数：15884 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

牛牛定义排序子序列为一个数组中一段连续的子序列,并且这段子序列是非递增或者非递减排序的。牛牛有一个长度为n的整数数组A,他现在有一个任务是把数组A分为若干段排序子序列,牛牛想知道他最少可以把这个数组分为几段排序子序列.
如样例所示,牛牛可以把数组A划分为[1,2,3]和[2,2,1]两个排序子序列,至少需要划分为2个排序子序列,所以输出2

输入描述:

输入的第一行为一个正整数n(1 ≤ n ≤ 10^5)

第二行包括n个整数A_i(1 ≤ A_i ≤ 10^9),表示数组A的每个数字。

输出描述:

输出一个整数表示牛牛可以将A最少划分为多少段排序子序列

示例1

输入

6
1 2 3 2 2 1

输出

算法知识视频讲解

→①年前↑


	import java.util.Scanner;



	



	//校招模拟：排序子序列



	public class Main {



	



	public static void main(String[] args) {



	// TODO Auto-generated method stub



	Scanner scanner = new Scanner(System.in);



	int n = scanner.nextInt();



	int[] data = new int[n];



	for(int i = 0; i < n; i++) {



	data[i]=scanner.nextInt();



	}



	int flag = 0;



	int result = 1;



	for(int i = 1; i < n; i++) {



	if(data[i]>data[i-1]) {



	if(flag==0) {



	flag = 1;



	}



	if(flag==-1) {



	flag = 0;



	result++;



	}



	}else if(data[i]<data[i-1]){



	if(flag == 0) {



	flag = -1;



	}



	if(flag == 1) {



	flag = 0;



	result++;



	}



	}



	}



	



	System.out.println(result);



	scanner.close();



	}



	



	}

编辑于 2017-05-21 16:21:43 回复(16)

元气の悟空

#include<stdio.h>
int main(){
    int a[100001],i,n,flag=0,res=1;
    for(scanf("%d",&n),i=0;i<n;i++) scanf("%d",a+i);
    for(i=1;i<n-1;i++){
        if(a[i]>a[i-1]&&a[i]>a[i+1]
           ||a[i]<a[i-1]&&a[i]<a[i+1]){
            res++;
            if(n-3!=i) i++;
        }
    }
    printf("%d\n",res);
}//找出波峰波谷

发表于 2017-11-11 00:46:03 回复(0)

牛客8017644号

下标从1到n-2，统计非相邻极值（a[i]>a[i-1]&&a[i]>a[i+1]||a[i]<a[i-1]&&a[i]<a[i+1]）的个数cnt
值得注意的是当上述循环最后一个极值下标为n-3时，需要判断下标为n-2的数是否为极值，如果是cnt+=1
最后输出cnt+1

import java.util.*;

public class Main{
    public static void main(String[] args){
       	Scanner scanner = new Scanner(System.in);
        int n =scanner.nextInt();
        int[] a = new int[n];
        for(int i=0;i<n;i++){
            a[i] = scanner.nextInt();
        }
        int cnt = 1;
        for(int i=1;i<n-1;i++){
            if(a[i]>a[i-1]&&a[i]>a[i+1]||a[i]<a[i-1]&&a[i]<a[i+1]){
                cnt++;
                if(n-3!=i){
                	i++;
                } 
            }
        }
        System.out.println(cnt);
    }
}

发表于 2017-06-08 16:59:02 回复(5)

喝醉了Ta的梦,晚安

#include<iostream>
#include<vector>
using namespace std;


int main()
{
    int n;
    cin>>n;
    vector<int> v;
    v.resize(n+1);
    v[n] = 0;
    for(int i=0;i<n;i++)
    {
        cin>>v[i];
    }
    
    int i=0;
    int count = 0;
    while(i<n)
    {
        if(v[i]<v[i+1])
        {
            while(i<n && v[i]<=v[i+1]){
                ++i;
            }
            ++count;
            ++i;
        }
        else if(v[i]==v[i+1])
        {
            ++i;
        }
        else{
            while(i<n && v[i]>=v[i+1]){
                ++i;
            }
            ++count;
            ++i;
        }
    }
    cout<<count<<endl;
    return 0;
}

发表于 2021-10-14 21:11:11 回复(0)

C/C++

梦向南

#include<iostream>

#include<vector>

using namespace std;

int ArrangeNumb(vector<int> &arr, int N)

{

int numb = 0;

int cont, cont1, cont2;

cont = cont1 = cont2 = 1;

for (int i = 0; i < N; i += cont)

{

for (int j = 0; i + j < N - 1; j++)//升序

{

if (arr[i + j + 1] < arr[i + j])

break;

cont1++;

}

for (int j = 0; i + j < N - 1; j++)//降序

{

if (arr[i + j + 1] > arr[i + j])

break;

cont2++;

}

(cont1 > cont2) ? (cont = cont1) : (cont = cont2);//取大者

cont1 = cont2 = 1;

numb++;

}

return numb;

}

int main()

{

int n;

cin >> n;

vector<int> str;//vector在堆上开辟内存，避免普通数组在栈上溢出

for (int i = 0, tep; i < n; i++)

{

cin>>tep;

str.push_back(tep);

}

cout << ArrangeNumb(str, n) << endl;

return 0;

}

发表于 2017-06-22 21:34:07 回复(0)

东方不败♂

#include <iostream>
using namespace std;
 
#define N 100001

bool isChange (int previous, int current, int next) {
    if ((current > previous && current > next) ||
        (current < previous && current < next)) {
        return true;
    }
    return false;
}

int main() {
    int n, arr[N];
    while (cin>>n) {
        int ans = 1, previous = 0;
        // 序列长度小于3，输出1
        if (n<3) cout << "1" << endl;
        for (int i=0; i<n; i++)
            cin >> arr[i];
        for (int i=1; i<n-1; i++) {
            // 当前数字与下一个数字相等，则跳过
            if (arr[i] == arr[i+1]) {
                continue;
            } else {
                // 若发生跳变，计数+1，指针+1。
                if (isChange(arr[previous], arr[i], arr[i+1])) {
                    ans++;
                    previous = ++i;
                } else {
                    previous = i-1;
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}

貌似没人和我一样，先占坑。

编辑于 2017-05-21 12:55:20 回复(3)

C/C++

pein531

贪心

如果发现当前元素与前一个元素相等就忽略；
如果当前元素大于上一个元素就做个标记，表示当前在形成单调不减序列；
如果当前元素小于上一个元素就做个标记，表示当前在形成单调不增序列。

如果在遍历的过程中发现当前元素与前一个元素的关系与标记不同，就说明单调部分已经结束，从当前位置开始要形成新的段。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
int n, a[N];

int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);
    int cnt = 1;
    bool asc = false, desc = false;
    for(int i = 1; i < n; i++) {
        if(a[i] == a[i - 1]) continue;
        if(!asc && !desc) {
            if(a[i] > a[i - 1]) asc = true;
            else desc = true;
        }else {
            if(asc && a[i - 1] > a[i]) {
                // 前面是单调不减，但此时出现递减趋势
                cnt++;
                asc = desc = false;
            }else if(desc && a[i - 1] < a[i]) {
                // 前面是单调不增，但此时出现递增趋势
                cnt++;
                asc = desc = false;
            }
        }
    }
    printf("%d", cnt);
    return 0;
}

发表于 2023-02-02 17:35:32 回复(0)

24届小菜只因

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int n;
    while(cin >> n)
    {
        if (n == 1) // 单个直接处理
        {
            cout << 1 << endl;
            continue;
        }
        vector<int> nums(n, 0);
        for (int i = 0; i < n; i++) cin >> nums[i];
        int i = 0, res = 0;

        while(i + 1 < n) 
        {
            if (nums[i] < nums[i + 1])// 非递减子序列
            {
                while(i + 1 < n && nums[i] <= nums[i + 1]) i++;
                res++, i++;// i++过掉当前子序列的最后一个。
                if (i == n - 1) res++, i++;// 恰好只剩一个数字
            }
            else if (nums[i] == nums[i + 1]) i++;
            else // 非递增子序列
            {
                while(i + 1 < n && nums[i] >= nums[i + 1]) i++;
                res++, i++;
                if (i == n - 1) res++, i++;// 恰好只剩一个数字
            }
        }
        cout<< res << endl;
    }
    return 0;
}

发表于 2023-01-28 01:59:00 回复(0)

程序员Andrew

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int n = 0;
    cin >> n;
    vector<int>v;
    //resize给多一个位置，避免越界
    v.resize(n+1);
    for(int i =0;i< n;i++)
    {
        cin>>v[i];
    } 
    int count = 0;
    int i = 0;
    while(i < n)
    {
        //进入非递减序列
        if(v[i]<v[i+1])
        {
            //要注意i的值，不能一直加
            while(v[i]<=v[i+1]&&i<n)
                i++;
            count++;
            //进入下一组
            i++;
        }
        else if (v[i]==v[i+1])
            i++;
        else
        {
            while(v[i]>=v[i+1]&&i<n)
                i++;
            count++;
            i++;
        }     
    }
    cout<<count;    
}

发表于 2022-10-14 15:47:53 回复(0)

C/C++

WeiC0der

#include<iostream>
#include<vector>
using namespace std;

int main(){
    int n;
    cin >> n;
    if(n == 1 || n == 2){
        cout << 1 << '\n';
        return 0;
    }
    vector<int> nums(n);
    for(int i = 0; i < n; ++i)
        cin >> nums[i];
    int whichState = nums[1] > nums[0] ? 1 : nums[1] == nums[0] ? 0 : -1;                        //1 代表严格递增状态；0 代表相等序列，即可以递增，也可以递减；-1 代表递减状态
    int count = 1;
    for(int i = 2; i < n; ++i){
        if(whichState == 0)
            //如果 nums[i] 前面的序列是状态 0
            whichState = nums[i] > nums[i - 1] ? 1 : nums[i] == nums[i - 1] ? 0 : -1;
        else if((whichState == 1 && nums[i] < nums[i - 1]) || (whichState == -1 && nums[i] > nums[i - 1])){
            //如果 nums[i] 前面的序列是递增，而 nums[i] 小于 nums[i-1]，则需要进行一次划分
            //如果 nums[i] 前面的序列是递减，而 nums[i] 大于 nums[i-1]，则需要进行一次划分
            whichState = (i < n - 1) ? (nums[i + 1] > nums[i] ? 1 : nums[i + 1] == nums[i] ? 0 : -1) : 1;
            ++count;
            ++i;
        }
    }
    cout << count << '\n';
    return 0;
}

看代码！

发表于 2021-08-11 18:44:00 回复(0)

Java

doi灬

import java.util.*;
public class Main {
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int[] ints = new int[scanner.nextInt()+1];//防止最后一个数是单独的一组数组长度多给一个最后让它和0比较
while(scanner.hasNext()){
for (int i = 0 ; i<ints.length-1 ; i++){ //因为数组长度多给了一个所以要i<ints.length-1
ints[i] = scanner.nextInt();
}

}

int sum = 0;

int i = 1;

//每次当 ints[i-1] 与 ints[i] 的关系发生改变的时候sum++

while(i < ints.length) {
if (ints[i-1] < ints[i]){
while (i < ints.length && ints[i-1] < ints[i] ){
i++;
}
sum++;
i++;
}else if (ints[i-1] == ints[i]){
i++;
}else {
while (i < ints.length && ints[i-1] > ints[i] ){
i++;
}
sum++;
i++;
}
}
System.out.println(sum);
}
}

发表于 2021-05-25 14:09:49 回复(0)

火的信仰叫梦想ii*

#include<iostream>
#include<vector>
using namespace std;

// 本题牛客测试用例不全，至少应该增加以下两组测试用例
// 输入：
// 4
// 1 3 2 3
// 输出：2

// 输入：
// 6
// 3 2 1 1 2 3
// 输出：2

int main() {
    int n;
    cin >> n;
// 注意这里多给了一个值，是处理越界的情况的比较，具体参考上面的解题思路
    vector<int> a;
    a.resize(n + 1);
    a[n] = 0;

//读入数组
    int i = 0;
    for (i = 0; i < n; ++i){
        cin >> a[i];
    }
i = 0;
    int count = 0;
    while (i < n){
    // 非递减子序列
        if (a[i] < a[i + 1]){
            while (i < n && a[i] <= a[i + 1]){
                i++;
            }
count++;
            i++;
        }
        else if (a[i] == a[i + 1]){
            i++;
        }
        else {
            // 非递增子序列
            while (i < n && a[i] >= a[i + 1]){
            i++;
        }
count++;
        i++;
        }
    }
cout << count << endl;
return 0;
}

发表于 2019-07-23 01:13:18 回复(0)

星儿123


	#include<iostream>
#include<vector>
using namespace std;



	int main()
{
    int n;
    cin>>n;
    vector<int> array;
    array.resize(n);
    //读入数组
    int i=0;
    for(i=0;i<n;++i)
        cin>>array[i];
    i=0;
    int k=0;
    int count=0;
    while(i<n)
    {
        if(array[i]<array[i+1] )
        {
            while(array[i]<=array[i+1])
            {
                i++;
            }
            k++;
            i++;
        }
        else if(array[i]==array[i+1])
            i++;
        else
        {
            while(array[i]>=array[i+1])
            {
                i++;
            }
            k++;
            i++;
        }
    }
    cout<<k;
    return 0;
    
}

发表于 2019-03-06 22:49:49 回复(2)

南邮kd

import java.util.*;
public class Main {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
        	int num=sc.nextInt();
        	int arr[]=new int[num];
        	int i=0;
        	while(i<num){
        		arr[i]=sc.nextInt();
        		i++;
        	}
        	int count=1;
        	int flag=0;   //表示位：0表示相等，1表示递增，-1表示递减；
        	for(int j=1;j<arr.length;j++){
        		if(arr[j]>arr[j-1]){
        			if(flag==0){
        				flag=1;
        			}else if(flag==-1){
        				flag=0;    //表示不符合条件,count++，回复初始值，进行下次循环判断;
        				count++;
        			}
        		}
        		if(arr[j]<arr[j-1]){
        			if(flag==0){
        				flag=-1;
        			}else if(flag==1){
        				flag=0;   //表示不符合条件,count++，回复初始值，进行下次循环判断;
        				count++;
        			}
        		}
        	}
        	System.out.println(count);
        }
        sc.close();
	}
}

发表于 2017-08-21 21:13:35 回复(0)

Asdil

def f(n, num):
    if n == 1:
        return 1
    ret = 1
    j = 0
    sub_num = [num[0]]
    for i in range(1, n):
        sub_num.append(num[i])
        sub_num.sort()
        if sub_num == num[j:i+1]:
            pass
        elif sub_num[::-1] == num[j:i+1]:
            sub_num= sub_num[::-1]
        else:
            ret += 1
            j = i
            sub_num = [num[i]]
    return ret
if __name__ == '__main__':
    while 1:
        try:
            n = int(raw_input())
            num = map(int, raw_input().split())
        except:
            break
        print f(n, num)

发表于 2017-07-18 10:02:12 回复(0)

C/C++

OFShare

#include <iostream>
using namespace std;

const int MAXN=100005;
int N;
int A[MAXN],res=0;

int f1(int i)	//非递减
{
    while((i!=N-1)&&A[i]<=A[i+1])
        ++i;
    return i;
}
int f2(int i)	//非递增
{
    while((i!=N-1)&&A[i]>=A[i+1])
        ++i;
    return i;
}
int main()
{
    cin>>N;
    for(int i=0;i<N;++i)
        cin>>A[i];
    int i=0;
    while(i!=N)
    {
        while(A[i]==A[i+1])		//相等就跳过
            ++i;
        if(A[i]<A[i+1])
            {i=f1(i)+1;++res;}
        else
            {i=f2(i)+1;++res;}
    }
    cout<<res<<endl;
    return 0;
}

发表于 2017-05-20 20:08:27 回复(0)

活跃的四郎在发呆

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n, arr[N];
int ret = 0;
int main() {
    cin >> n;
    for(int i = 0; i < n; i++) cin >> arr[i];

    for(int i = 0; i < n; i++)
    {
        if(i == n - 1)
        {
            ret++;
            break;
        }

        if(arr[i] > arr[i + 1])
        {
            while(i + 1 < n && arr[i] >= arr[i + 1]) i++;
            ret++;
        }
        else if(arr[i] < arr[i + 1])
        {
            while(i + 1 < n && arr[i] <= arr[i + 1]) i++;
            ret++;
        }
    }
    cout << ret << endl;
}
// 64 位输出请用 printf("%lld")

发表于 2025-08-08 10:43:44 回复(0)

roboko_

#include <bits/stdc++.h>

using namespace std;

int n;

vector<int> nums;

int main()

{

cin >> n;

nums.resize(n);

for(int i=0;i<n;++i)

{

cin >> nums[i];

}

int ret = 0;

//将连续非递增或非递减视为一段连续区域

//i是这段区域的起点

for(int i = 0; i < n; ++i)

{

int j = i + 1;

//j找递增最长子数组

for(;j < n && nums[j] >= nums[j - 1]; ++j);

int t = i + 1;

//t找递减最长子数组

for(;t < n && nums[t] <= nums[t - 1]; ++t);

//出循环后，j和t都指向各自满足条件的下一个，要将i减一，这样for循环

//再次将i加一后，i指向的就是下一段区域的起点

i = max(j, t) - 1;

++ret;

}

cout << ret << endl;

return 0;

}

// 64 位输出请用 printf("%lld")

发表于 2025-08-04 23:03:51 回复(0)

C/C++

申目

#include <iostream>
#include <vector>

int main()
{
    int n,ret = 0;std::cin>>n;
    std::vector<int> arr(n);
    for(int i = 0;i<n;i++) std::cin>>arr[i];
    int left = 0,right = 1;
    while(right <n)
    {
        int flag = -1;
        while(right < n && arr[right] - arr[left] == 0)
        {
            right++;
            left++;
        }
        //到这里说明right和left处的值是不同的
        while(right < n && arr[right] - arr[left] > 0) 
        {
            flag = 1;
            right++;
            left++;
        }

        if(flag == 1)
        {
            right ++;
            left++;
            ret++;
        }
        while(right < n && arr[right] - arr[left] < 0)
        {
            flag = 0;
            right++;
            left++;
        }
        if(flag == 0)
        {
            right++;
            left++;
            ret++;
        }
    }
    if(left == n-1) ret++;
    std::cout<<ret<<std::endl;
    return 0;
}

滑动窗口

发表于 2025-05-25 15:58:29 回复(0)

Surtr1

#include <iostream>

#include<vector>

using namespace std;

int main() {

int n;

cin>>n;

vector<int> a(n+1);

for(int i=1;i<=n;i++)cin>>a[i];

int i =2;

int res =0;

while(i<=n)

{

if(a[i]>a[i-1])

{

res++;

while(a[i-1]<=a[i]&&i<=n)

{

i++;

}

else if(a[i]<a[i-1])

{

res++;

while(a[i-1]>=a[i]&&i<=n)

{

i++;

}

else

{

while(a[i]==a[i-1]&&i<=n)i++;

}

if(i==n)

{

res++;

break;

}

i++;

// cout<<i<<' '<<res<<endl;

}

cout<<res;

}

// 64 位输出请用 printf(\"%lld\")

发表于 2024-08-09 23:14:22 回复(0)

提交观点

问题信息

C++工程师 golang工程师 2017 iOS工程师安卓工程师运维工程师前端工程师算法工程师测试工程师 PHP工程师安全工程师游戏研发工程师 c#工程师数据库工程师信息技术岗贪心区块链测试开发工程师 2020 大数据开发工程师数据分析师 Java工程师牛客

来自：【2017】牛客模考（...

难度：

79条回答 134收藏 32770浏览

通过挑战的用户

活跃的美羊羊求实习

2023-03-15 09:36:53
牛客82556...

2023-03-13 23:36:38
颓废小牛

2023-03-12 23:29:24
牛客23890...

2023-03-12 20:07:05
李逢溪

2023-03-12 17:24:03

排序子序列

输入描述:

输出描述:

输入

输出

贪心

问题信息

热门推荐

通过挑战的用户

相关试题