首页 > 试题广场 >

排序子序列

[编程题]排序子序列
  • 热度指数：15247 时间限制：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

输出

2
算法知识视频讲解
添加回答
→①年前↑头像 →①年前↑ 

	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号头像 牛客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的梦,晚安头像 喝醉了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头像 pein531

贪心

  1. 如果发现当前元素与前一个元素相等就忽略；
  2. 如果当前元素大于上一个元素就做个标记，表示当前在形成单调不减序列；
  3. 如果当前元素小于上一个元素就做个标记，表示当前在形成单调不增序列。
如果在遍历的过程中发现当前元素与前一个元素的关系与标记不同，就说明单调部分已经结束，从当前位置开始要形成新的段。 
#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届小菜只因头像 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头像 程序员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头像 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灬头像 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*头像 火的信仰叫梦想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头像 星儿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头像 南邮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头像 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头像 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)
Surtr1头像 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)
睲涳头像 睲涳 
#include<iostream>
#include<vector>
using namespace std;

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;
}


编辑于 2024-01-28 23:14:13 回复(0)
牛客246368028号头像 牛客246368028号
 
    
#include<iostream>
#include<vector>
using namespace std;
int main()
{
	int n = 0,x=0,count=0;
	cin >> n;
	vector<int> group;
	group.resize(n+1);
	group[n] = 0;
	for (int i = 0; i < n; i++)
	{
		cin >> group[i];
	}
	while (x < n)
	{
		if (x<n&&group[x] < group[x + 1])
		{
			while(group[x] < group[x + 1])
			{
				x++;
			}
			count++;
		}
		else if (group[x] > group[x + 1])
		{
			while (x<n&&group[x] > group[x + 1])
			{
				x++;
			}
			count++;
		}
		else
		{
			x++;
		}
		x++;

	}
	cout << count << endl;
	return 0;
}

发表于 2023-10-24 16:33:38 回复(1)
迷梦a头像 迷梦a
这叫子序列？？？
发表于 2023-10-10 20:11:49 回复(0)
提交观点

问题信息

C++工程师 golang工程师 2017 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 安全工程师 游戏研发工程师 c#工程师 数据库工程师 信息技术岗 贪心 区块链 测试开发工程师 2020 大数据开发工程师 数据分析师 Java工程师 牛客
来自：【2017】牛客模考（...
难度：
76条回答 28686浏览

热门推荐

通过挑战的用户

相关试题

排序子序列

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号