首页 > 试题广场 >

查找二叉搜索树的叶子节点

[编程题]查找二叉搜索树的叶子节点
  • 热度指数:1456 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解

给一个二叉查找树(Binary Search Tree)的前序遍历结果数组,打印出所有的叶子节点。


输入描述:

输入为二叉查找树的前序遍历结果数组,元素之间用空格分隔:

9 8 7 10



输出描述:

所有的叶子节点元素,用空格分隔

解释:因为二叉搜索树的表示为:

       9

   8    10

7

输出的叶子节点为: 7 10

示例1

输入

9 8 7 10

输出

7 10
数组第一个是根,分割它
找到 分离左右子树的 index
如果最后的子树只剩下一个,那他就是叶子
#include <vector>
#include <string>
#include <iostream>
using namespace std;

int findindex(int start, int end, vector<int>& a, int target) {
    int i;
    for (i = start; i <= end; ++i) {
        if (a[i] > target) return i;
    }
    return i;
}

void shit(int start, int end, vector<int>& a) {
    // cout << start << end << endl;
    if (start > end) return;
    else if (start == end) {
        cout << a[start] << " ";
        return;
    }
    else {
        int index = findindex(start+1, end, a, a[start]);
        if (index <= end) {
            shit(start+1, index-1, a);
            shit(index, end, a);
        }
        else {
            shit(start+1, index-1, a);
        }
        
    }
}

int main() {
    vector<int> gyh;
    char c;
    int t;
    do {
        scanf("%d", &t);
        gyh.push_back(t);
        scanf("%c", &c);
    } while (c == ' ');
    shit(0, gyh.size()-1, gyh);
}



发表于 2021-03-06 15:24:13 回复(2)
单调栈思路,O(n)时间复杂度:
遍历二叉搜索树的前序序列,同时维护一个单独递减栈,比较当前遍历到的元素cur与栈顶元素top
  • 若 cur < top,则说明cur是top的左节点;
  • 若 cur > top,不断出栈,直到cur < top,这时,cur 是 最后一个出栈的元素 的右子节点。
利用以上两个特性,可以找到二叉搜索树中所有非叶子节点,剩下的就是叶子结点了。
vector<int> findLeaves(vector<int>& arr) {
    unordered_set<int> non_leaves;
    stack<int> nodes;
    nodes.push(arr[0]);
 
    for (int i = 1; i < arr.size(); i++) {
        if (arr[i] < nodes.top()) {  // arr[i]是 nodes.top()的左子节点
            non_leaves.insert(nodes.top());
            nodes.push(arr[i]);
        }
        else {
            int t;
            while (!nodes.empty() && arr[i] > nodes.top()) {
                t = nodes.top();
                nodes.pop();
            }
            nodes.push(arr[i]);
            non_leaves.insert(t); // arr[i]是最后一次出栈的元素的右子节点
        }
    }
    vector<int> res;
    for (int i : arr) {
        if (!non_leaves.count(i))
            res.push_back(i);
    }
 
    return res;
}


编辑于 2021-07-18 21:12:12 回复(1)
#include <iostream>
#include <vector>
#include <sstream>
#include <deque>

using namespace std;
class Solution{
public:
    vector<int> seachBinaryTreeLeave(vector<int>& nums){
        if(nums.size()==1) return nums;
        vector<int> ans;
        int tmp=0;
        deque<int> board;
        for(int i=0;i<nums.size();i++){
            if(!board.empty()&&nums[i]>board.back()&&board.back()<board.front()){
                ans.push_back(board.back());
                while(!board.empty()&&board.back()<nums[i]) board.pop_back();
            }
            board.push_back(nums[i]);
        }
        if(!board.empty()) ans.push_back(board.back());
        return ans;
    }
};

int main(int argc,char* argv[]){
    vector<int> nums;
    string str;
    getline(cin,str);
    stringstream s(str);
    int num;
    while(s>>num) nums.emplace_back(num);

    vector<int> ans=Solution().seachBinaryTreeLeave(nums);
    for(int i=0;i<ans.size();i++){
        cout<<ans[i];
        if(i!=ans.size()-1) cout<<" ";
    }
    cout<<endl;
    return 0;
}
比较简练的算法,利用双端队列deque存储二叉搜索树的值,首先先理解下二叉搜索树的定义:是一颗空树或者非空树,若它的左子树不为空,
则它的左子树都小于它的根节点,若它的右子树不为空,则它的右子树都大于它的根节点。此外二叉树的前序遍历的规则是:根左右。这样可以推测出初始状态为递减序列,若出现一个大于前面的元素的值,则可以断定前面的值为叶子节点。因此可以根据这个性质,每次枚举先存入到deque中,先判断前面元素与当前元素的情况,
board.back()<board.front(),这句话为了判断是否转换到右子树了
若满足叶子节点,则存储结果,然后再while循环,维持一个递减序列。最后还要判断deque中是否还有元素,因为最右端还有一个元素
编辑于 2021-04-04 20:03:59 回复(1)
二叉搜索树的中序序列是单调递增的,因此可以先利用中序和先序序列重构二叉搜索树,然后再先序遍历它,在遍历的过程中将左右孩子均为空的节点值输出即可(必须先序遍历,否则顺序与后台不一致AC不了)
class TreeNode(object):
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def reConstructBinaryTree(pre, tin):
    if len(pre) == 0:
        return
    elif len(pre) == 1:
        return TreeNode(pre[0])
    else:
        tree = TreeNode(pre[0])
        idx = tin.index(pre[0])
        tree.left = reConstructBinaryTree(pre[1:idx + 1], tin[:idx])
        tree.right = reConstructBinaryTree(pre[idx + 1:], tin[idx + 1:])
    return tree


def preorderTraversal(root):
    if not root:
        return
    stack = [root]
    while stack:
        node = stack.pop()
        if node.left is None and node.right is None:
            print(node.val, end=" ")
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)


if __name__ == "__main__":
    preorder = list(map(int, input().split()))
    inorder = sorted(preorder)
    tree = reConstructBinaryTree(preorder, inorder)
    preorderTraversal(tree)

发表于 2021-07-23 18:35:49 回复(2)
import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] s = sc.nextLine().split(" ");
        int[] arr = new int[s.length];
        for(int i=0; i<s.length; i++){
            arr[i] = Integer.parseInt(s[i]);
        }
        String res = binarySearchTree(arr,0,arr.length-1);
        System.out.println(res.substring(0,res.length()-1));
    }

    public static String binarySearchTree(int[] arr, int start, int end){
        if(start == end){
            return String.valueOf(arr[start] + " ");
        }
        int index = start;
        boolean flag = false;
        for(int i = start; i <= end; i++){
            if(arr[i] > arr[start]) {
                flag = true;
                index = i;
                break;
            }
        }
        if(flag){
            return binarySearchTree(arr, start+1,index-1) + binarySearchTree(arr, index, end);
        } else {
            return binarySearchTree(arr, start+1,end);
        }
    }
}
发表于 2021-03-23 22:52:41 回复(0)

Go 递归,思路:在前序遍历结果中,第一个大于根节点的即为右子树,在这之前的为左子树

package main
 
import "fmt"
import "io"
 
func main() {
    var input int
    preOrder := []int{}
    for {
        _, err := fmt.Scan(&input)
        if err == io.EOF {
            break
        }
        preOrder = append(preOrder, input)
    }
    findLeafNode(preOrder, 0, len(preOrder) - 1)
}
 
func findLeafNode(arr []int, left, right int) {
    // 当在前序结果中范围缩小到一个值时,代表就是叶子节点
    if left == right {
        fmt.Print(arr[left])
        fmt.Print(" ")
        return
    }
    i := left + 1
    // 开始遍历前序结果,寻找左右子树分界线(比根节点大的就是分界线)
    for ; i <= right; i++ {
        if arr[i] > arr[left] {
            // 如果第一个节点就比根节点大,说明全是右子树
            if i == left {
                findLeafNode(arr, i + 1, right)
            } else {
                findLeafNode(arr, left + 1, i - 1)
                findLeafNode(arr, i, right) 
            }
            break
        }
        // 没有比根节点大的,说明全是左子树
        if i == right {
            findLeafNode(arr, left + 1, right)
        }
    }
}
编辑于 2021-05-16 03:21:22 回复(0)
模拟前序遍历,找到左右子树的范围,若子树只有一个节点,加入到结果集。

import java.util.*;

public class Main {

        private static List<Integer> res;
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            String s = sc.nextLine();
            sc.close();

            String[] ss = s.split(" ");
            int n = ss.length;
            int[] nums = new int[n];
            res = new ArrayList<>();

            for (int i = 0; i < n; i++) {
                nums[i] = Integer.parseInt(ss[i]);
            }

            dfs(nums, 0, n - 1);
            for (int r: res) {
                System.out.print(r + " ");
            }
        }

        private static void dfs(int[] nums, int left, int right) {
            if (left == right) {
                res.add(nums[left]);
                return;
            } else if (left > right) {
                return;
            }
            int root = nums[left];
            //找到右子树的起点
            int rightStart = left + 1;
            for (int i = left + 1; i <= right; i++) {
                if (nums[i] > root) {
                    rightStart = i;
                    break;
                }
            }
            if (nums[rightStart] > root) {
                dfs(nums, left + 1, rightStart - 1);
                dfs(nums, rightStart, right);
            } else {
                 dfs(nums, left + 1, right);   
            }
        }
    }

发表于 2022-03-28 10:03:10 回复(0)
不用很复杂吧
s = list(map(int, input().split()))
res = []
def dfs(path):
    if not path : return 
    if len(path) == 1:
        print(path[0], end=' ')
    i = 1
    while i < len(path) and path[i] < path[0]:
        i += 1
    left = path[1:i]
    right = path[i:]
    dfs(left)
    dfs(right)
dfs(s)
      

发表于 2022-03-19 22:10:28 回复(0)
import java.io.*;
import java.util.*;



public class Main {
    static StringBuilder sb=new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        String[] s=str.split(" ");
        int[] num=new int[s.length];
        for(int i=0;i<s.length;i++){
            num[i]=Integer.parseInt(s[i]);
        }
        helper(num,0,s.length-1);
        System.out.println(sb.toString());
    }

    private static void helper(int[] num,int root,int right){
        if(root==right){
            sb.append(num[root]).append(' ');
            return;
        }
        boolean flag=true;
        int left=0;
        for(int i=root;i<=right;i++){
            if(num[i]>num[root]&&flag){
                left=i;
                flag=false;
            }
        }
        //只有一边子树
        if(flag||left==root+1){
            helper(num,root+1,right);
        }
        //有两边树
        else {
            helper(num,root+1,left-1);
            helper(num,left,right);
        }
    }
}

发表于 2021-09-07 16:16:08 回复(0)
#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_map>

using namespace std;

unordered_map<int, int> qtoz;

void dfs(vector<int>& qf, vector<int>& zf, int l1, int r1, int l2, int r2, vector<int>& res) {
	if (l1 > r1 || l2 > r2) return;
	if (l1 == r1) {
		res.push_back(qf[l1]);
		return;
	}
	int root = qf[l1];
	int k = qtoz[root], m = k - l2;
	dfs(qf, zf, l1 + 1, l1 + m, l2, k - 1, res);
	dfs(qf, zf, l1 + m + 1, r1, k + 1, r2, res);
}

int main() {
	vector<int> qf;
	int a = 0;
	while (cin >> a) {
		qf.push_back(a);
		while (getchar() != '\n') {
			cin >> a;
			qf.push_back(a);
		}
		vector<int> zf(qf.begin(), qf.end());
		sort(zf.begin(), zf.end());
		for (int i = 0; i < qf.size(); i++) {
			for (int j = 0; j < zf.size(); j++) {
				if (qf[i] == zf[j]) {
					qtoz[qf[i]] = j;
					break;
				}
			}
		}
		vector<int> res;
		dfs(qf, zf, 0, qf.size() - 1, 0, zf.size() - 1, res);
		for (int i = 0; i < res.size(); i++) cout << res[i] << ' ';
		cout << endl;
		qf.clear();
	}
	return 0;
}
二叉查找树的中序遍历是递增数组,将输入的前序序列进行排序可得到中序遍历数组,根据前序和中序遍历序列可还原二叉树,则可找到所有的叶子节点。
发表于 2021-07-27 21:21:45 回复(0)
s = input().split(' ')
preOrd = list(map(int, s)) #[8 5 1 7 10 12]
inOrd = sorted(preOrd) # [1 5 7 8 10 12]
res = []
def leafNode(pre_, in_):
    if not pre_ or not in_:
        return
    if len(in_) == 1:
        res.append(in_[0])
    root = pre_.pop(0)
    index_ = in_.index(root)
    leafNode(pre_, in_[:index_])
    leafNode(pre_, in_[index_+1:])
    return
    
leafNode(preOrd, inOrd)
res = list(map(str, res))
print(' '.join(res))
发表于 2021-07-16 20:49:38 回复(0)
C++从前序遍历建树,可以顺手把答案输出了。
其实也可以建树完成后用BFS搜索叶子节点,但是没必要,而且会增加额外开销,最坑的是叶子节点的输出顺序问题会导致用例通过3/5
#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
 
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int val_): val(val_), left(nullptr), right(nullptr) {}
};
 
TreeNode* buildTree(vector<int>& nums, int start, int end, vector<int>& ans)
{
    if (start >= end) return nullptr;
    TreeNode* node = new TreeNode(nums[start]);
    //cout << start << " " << node->val << endl;
    int lbegin = nums[start + 1] < nums[start] ? start + 1: start;
    int rbegin = end;
    for (int i = lbegin + 1; i < end; i++)
    {
        if (nums[i] > nums[start]) {
            rbegin = i;
            break;
        }
    }
    if (lbegin > start) node->left = buildTree(nums, lbegin, rbegin, ans);
    if (rbegin < end) node->right = buildTree(nums, rbegin, end, ans);
    if (node->left == nullptr && node->right == nullptr) ans.push_back(node->val);
    return node;
};
 
int main()
{
    vector<int> nums;
    int num;
    while (cin >> num)
    {
        nums.push_back(num);
    }
    int len = nums.size();
    vector<int> ans;
    TreeNode* root = buildTree(nums, 0, len, ans);
    // bfs
    //queue<TreeNode*> q;
    //q.push(root);
    //vector<int> ans;
    //while (!q.empty())
    //{
    //    int size_ = q.size();
    //    for (int i = 0; i < size_; i++)
    //    {
    //        TreeNode* tmp = q.front();
    //        q.pop();
    //       if (tmp->left == nullptr && tmp->right == nullptr) ans.push_back(tmp->val);
    //        else{
    //            if (tmp->left) q.push(tmp->left);
    //            if (tmp->right) q.push(tmp->right);
    //        }
    //    }
    //}
    for (auto i : ans) cout << i << " ";
    return 0;
}


发表于 2021-07-12 17:22:43 回复(0)
#include <iostream>
#include <vector>
#include <functional>
using namespace std;
 
int main() {
    int num;
    vector<int> nums;
    while (cin >> num) {
        nums.push_back(num);
    }
    vector<int> res;
    function<void(int,int)> findleaf = [&](int l, int r) {
        int cur = nums[l];
        int left = -1, right = -1;
        for (int j = l+1; j < r; j++) {
            if (nums[j] < cur && left == -1) left = j;
            if (nums[j] > cur && right == -1) right = j;
        }
        if (left == -1 && right == -1) {
            res.push_back(cur);
            return;
        }
        if (left == -1) {
            findleaf(right, r);
        } else if (right == -1) {
            findleaf(left, r);
        } else {
            findleaf(left, right);
            findleaf(right, r);
        }
    };
     
    findleaf(0, nums.size());
    for (auto i : res)
        cout << i << " ";
     
    return 0;
}


找到左右子树的root,递归即可
发表于 2021-06-29 10:48:18 回复(0)
import java.lang.*;
import java.util.*;

public class Main{
      static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int val){
            this.val = val;
        }
    }
    
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        String[] strs = scanner.nextLine().split(" ");
        int[] ints = new int[strs.length];
        for(int i = 0; i < strs.length; i++){
            ints[i] = Integer.valueOf(strs[i]);
        }
        TreeNode root = new TreeNode(ints[0]);
        for(int i = 1; i < ints.length; i++){
            insert(ints[i], root);
        }
        List<Integer> ret = new ArrayList<>();
        back(root, ret);
        for(int i = 0; i < ret.size(); i++){
            System.out.print(ret.get(i) + " ");
        }
    }
    
    public static void back(TreeNode root, List<Integer> ret){
        if(root.left == null && root.right == null){
            ret.add(root.val);
        }
        if(root.left != null){
            back(root.left, ret);
        }
        if(root.right != null){
            back(root.right, ret);
        }
    }
    
    public static void insert(int val, TreeNode root){
          if(val < root.val){
              if(root.left == null){
                  root.left = new TreeNode(val);
              }else{
                  insert(val, root.left);
              }
          }else{
              if(root.right == null){
                  root.right = new TreeNode(val);
              }else{
                  insert(val, root.right);
              }
          }
    }
}
构造一下二叉树再查找
发表于 2021-05-09 15:13:00 回复(0)
#include<bits/stdc++.h>
using namespace std;
int main(){
    vector<int>array;
    int i,k=1;
    cin>>i;
    array.push_back(i);
    while(cin.get()!='\n'){
        cin>>i;
        k++;
        array.push_back(i);
    }
    for(int j=1;j<=k;j++){
        if(array[j]>array[j-1]){cout<<array[j-1]<<' ';}
    }
    cout<<array[k-1];
    return 0;
}
秒杀!!!
编辑于 2021-05-06 17:14:13 回复(0)
tree=list(map(int,input().split()))
#tree=[40, 31, 25, 20, 26, 33, 50, 42, 53]
def findt(tree):
    if len(tree)<2:
        #return str(tree)
        return tree
    i=1
    while (i<len(tree)) and tree[i]<=tree[0]:
        i+=1
    if i==len(tree):
        return [tree[-1]]
    else:
        return findt(tree[1:i])+findt(tree[i:])
a=findt(tree)
a=list(map(str,a))
#for i in a:
#    res+=' '+str(i)
#print(res)
print(' '.join(a))
二叉搜索树:空树或者满足下列条件:

若左子树不空,则左子树上所有结点的值都小于根节点。
若右子树不空,则右子树上所有结点的值都大于根节点。
为了判断一个数组是否为一棵二叉搜索树的前序遍历,主要思想为:因前序遍历第一个遍历的是根节点,则数组第一个数为根节点的值,再基于根节点把整棵树的遍历序列分成左子树和右子树序列,递归的处理这两个子序列。

发表于 2021-04-19 17:54:50 回复(0)
const readline = require('readline')
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
})

const results = []

rl.on('line',str=>{
    const nodes = str.split(' ').map(item=>{
        return parseInt(item)
    })
    const bt = createBT(nodes)
    traverse(bt, 1)
    
    console.log(results.join(' '))
})



function createBT(nodes){
    const bt = []
    nodes.forEach(node=>{
        insertNode(bt, node, 1)
    })
    return bt
}


function insertNode(bt, node, i){
    if(!bt[i]){
        bt[i] = node
        return
    }
    //递归
    if(node < bt[i]){
        insertNode(bt, node, 2*i)
    }else{
        insertNode(bt, node, 2*i+1)
    }
}

//遍历
function traverse(bt, i){
    if(!bt[i]){
        return 
    }
    //只打印叶子节点
    if(!bt[2*i] && !bt[2*i+1]){
        //console.log(bt[i])
        results.push(bt[i])
    }
    traverse(bt, 2*i)
    traverse(bt, 2*i+1)
}

发表于 2021-04-04 20:45:40 回复(0)
递归解法
import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.Scanner;

/**
 * FindLeafNode class
 *
 * @author Soarkey
 * @date 2021/3/26
 */
public class Main {
    private static Queue<Integer> queue;

    public static void main(String[] args) {
        Scanner in = new Scanner(new BufferedInputStream(System.in));
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));

        while (in.hasNextInt()) {
            String s = in.nextLine();
            findLeafNode(s);
            int n = queue.size();
            for (int i = 0; i < n - 1; ++i) {
                out.print(queue.poll() + " ");
            }
            out.println(queue.poll());
        }

        in.close();
        out.close();
    }

    public static void findLeafNode(String s) {
        String[] sp = s.split(" ");
        int n = sp.length;
        int[] preOrder = new int[n];
        for (int i = 0; i < n; ++i) {
            preOrder[i] = Integer.parseInt(sp[i]);
        }

        int[] inOrder = new int[n];
        System.arraycopy(preOrder, 0, inOrder, 0, n);
        Arrays.sort(inOrder);

        queue = new ArrayDeque<>(n - 1);
        buildBinarySearchTree(preOrder, 0, n - 1, inOrder, 0, n - 1);
    }

    public static void buildBinarySearchTree(int[] preOrder, int l1, int r1, int[] inOrder, int l2, int r2) {
        if (l1 > r1 || l2 > r2) {
            return;
        }

        int root = preOrder[l1];
        int k = l2;
        for (int i = l2; i <= r2; ++i) {
            if (inOrder[i] == root) {
                k = i;
                break;
            }
        }

        boolean isLeafNode = true;
        if (k > l2) {
            // left child
            isLeafNode = false;
            buildBinarySearchTree(preOrder, l1 + 1, l1 + k - l2, inOrder, l2, k - 1);
        }
        if (k < r2) {
            // right child
            isLeafNode = false;
            buildBinarySearchTree(preOrder, l1 + k - l2 + 1, r1, inOrder, k + 1, r2);
        }
        if (isLeafNode) {
            queue.add(root);
        }
    }
}


发表于 2021-03-26 21:13:16 回复(0)
分而治之
#include <bits/stdc++.h>
 
using namespace std;
 
vector<int> res;
 
void getRes(vector<int>& left, vector<int>& right) {
    //int cnt = 0;
    int l = left.size(), r = right.size();
    if (l == 1) {
        res.emplace_back(left[0]);
    } else if (l > 1) {
        vector<int> lleft, lright;
        int root = left[0];
        for (int i = 1; i < l; ++i) {
            if (left[i] < root) {
                lleft.emplace_back(left[i]);
            } else {
                lright.emplace_back(left[i]);
            }
        }
        getRes(lleft, lright);
    }
     
    if (r == 1) {
        res.emplace_back(right[0]);
    } else if (r > 1){
        vector<int> rleft, rright;
        int root = right[0];
        for (int i = 1; i < r; ++i) {
            if (right[i] < root) {
                rleft.emplace_back(right[i]);
            } else {
                rright.emplace_back(right[i]);
            }
        }
        getRes(rleft, rright);
    }
     
    //return cnt;
}
 
int main() {
    vector<int> left, right;
    int root;
    scanf("%d", &root);
    int val;
    while (~scanf("%d", &val)) {
        if (val < root) {
            left.emplace_back(val);
        } else {
            right.emplace_back(val);
        }
    }
    if (left.size() == 0 && right.size() == 0) {
        cout << root;
        return 0;
    }
    getRes(left, right);
     
    for (int i = 0; i < res.size(); ++i) {
        cout << res[i] << ' ';
    }
     
     
    return 0;
}


发表于 2021-03-22 22:08:18 回复(0)

/排除法/

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        ArrayList<Integer> arr=new ArrayList<>();
        Scanner sr=new Scanner(System.in);
        String s=sr.nextLine();
        StringBuilder sb=new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i)!=' ') {
                sb.append(s.charAt(i));
            }else {
                arr.add(Integer.parseInt(sb.toString() + ""));
                sb.setLength(0);
            }
        }
        arr.add(Integer.parseInt(sb.toString() + ""));
        solution(arr);
    }
    public static void solution(ArrayList<Integer> arr){
        boolean[] brr=new boolean[arr.size()];
        for (int i = 1; i < arr.size(); i++) {
            if (arr.get(i)<=arr.get(i-1))brr[i-1]=true;
            else {
                int tem=i-1;
                for (int j = i-1; j >=0 ; j--) {
                    if (arr.get(j)>arr.get(tem)&&arr.get(j)<arr.get(i)){
                        tem=j;
                    }
                }
                    brr[tem]=true;
            }
        }
        for (int i = 0; i < arr.size(); i++) {
            if (!brr[i]) System.out.print(arr.get(i)+" ");
        }
    }
}
编辑于 2021-03-20 22:57:49 回复(0)