算法合集 | 神奇的笛卡尔树 - HDU 1506

笛卡尔树是一个很有意思的树形结构,因为它同时满足两个性质,从key(key就是索引位置,如下图中9的key为1,3的key为2......)来看,满足二叉搜索树的特性,从value来看,满足堆的性质。

重点参考下图,图片来自维基百科,还算是能够比较形象的说明这两点。

笛卡尔树拥有这两种特性,那么它有什么用途呢?

对于HDU 1506,我们需要计算最大矩形区域,正好是笛卡尔树最典型的用途,从上图中,我们以任意节点K开始,K所在的最大矩形必定是K的value为高,K的右子树最大key值减去K的key值为宽。

笛卡尔树比较难的地方在于构造,小编我是看了好久才把这个思路理清,这里给出大概的思路,不懂得童鞋留言讨论。

1、笛卡尔树的构造:

(1)从第一个元素开始,从左往右遍历数组L

(2)将元素L[0]作为树的根节点R

(3)for i in [a[1], a[2]...a[n]]

(4)如果a[i]小于根节点R,则将a[i]作为根节点R的父节点

(5)如果a[i]大于根节点R,则将a[i]从根节点的右节点开始寻找位置

(6)从右寻找的逻辑同根节点的对比方法

2、特性

对于树上的每个节点,以它作为高的新矩形的面积就是以该节点为根的子树大小乘以它的高

构造源代码:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct node_s
{
    struct node_s * l;
    struct node_s * r;
    struct node_s * p;
    int v;
}node_t;

typedef struct tree_s
{
    node_t * root;
}tree_t;

node_t * node_create(node_t * p, int v)
{
    node_t * n = (node_t*)malloc(sizeof(node_t));
    memset(n, 0, sizeof(node_t));
    n->v = v;
    n->p = p;
    return n;
}

tree_t * tree_create()
{
    tree_t * t = (tree_t*)malloc(sizeof(tree_t));
    memset(t, 0, sizeof(tree_t));
    return t;
}

void tree_insert_n(node_t * root, int v)
{
    //当前节点比根节点小,则转换为根节点
    if(v < root->v){
        node_t * n = node_create(root->p, v);
        root->p->r = n;
        root->p = n;
        n->l = root;
    }else{
        //如果右子树不存在,直接放置
        if(root->r == 0){
            root->r = node_create(root, v);
            return;
        }
        //当前的节点比根节点大,则从根节点的右子树开始查找
        tree_insert_n(root->r, v);
    }
}

void tree_insert(tree_t * t, int v)
{
    if(t->root == 0){
        t->root = node_create(0, v);
        return;
    }

    //当前节点比根节点小,则转换为根节点
    if(v < t->root->v){
        node_t * n = node_create(0, v);
        t->root->p = n;
        n->l = t->root;
        t->root = n;
    }else{
        //如果右子树不存在,直接放置
        if(t->root->r == 0){
            t->root->r = node_create(t->root, v);
            return;
        }
        //当前的节点比根节点大,则从根节点的右子树开始查找
        tree_insert_n(t->root->r, v);
    }
}

void tree_print_n(node_t * n, int level, char dir)
{
    if(!n){
        return;
    }
    for(int i=0; i<level; ++i){
        printf("---");
    }
    printf("%c--%d\n", dir, n->v);
    tree_print_n(n->l, level+1, 'L');
    tree_print_n(n->r, level+1, 'R');
}

void tree_print(tree_t * tree)
{
    tree_print_n(tree->root, 0, 'C');
    printf("\n");
}

void tree_free(tree_t * t)
{

}

int main()
{
    freopen("test.txt", "r", stdin);

    int n, height;

    while (scanf("%d", &n), n)
    {
        int arr[n];

        tree_t * tree = tree_create();

        for (int i = 0; i < n; i++)
        {
            scanf("%d", &arr[i]);
        }

        for (int i = 0; i < n; ++i)
        {
            tree_insert(tree, arr[i]);
            tree_print(tree);
        }

        tree_free(tree);

        printf("\n");
    }

    return 0;
}

在理解了笛卡尔树的构造之后,HDU 1506这道题就很容易理解了。具体的解题思路就不细讲了,只不过下面这个代码在构造笛卡尔树的时候用了数组形式,如果一时理解不了以后再看也行,重点是把上面的代码弄清楚。

来看题~~

Problem Description

A histogram is a polygon composed of a sequence of rectangles aligned at a common base line. The rectangles have equal widths but may have different heights. For example, the figure on the left shows the histogram that consists of rectangles with the heights 2, 1, 4, 5, 1, 3, 3, measured in units where 1 is the width of the rectangles:

Usually, histograms are used to represent discrete distributions, e.g., the frequencies of characters in texts. Note that the order of the rectangles, i.e., their heights, is important. Calculate the area of the largest rectangle in a histogram that is aligned at the common base line, too. The figure on the right shows the largest aligned rectangle for the depicted histogram.

Input

The input contains several test cases. Each test case describes a histogram and starts with an integer n, denoting the number of rectangles it is composed of. You may assume that 1 <= n <= 100000. Then follow n integers h1, ..., hn, where 0 <= hi <= 1000000000. These numbers denote the heights of the rectangles of the histogram in left-to-right order. The width of each rectangle is 1. A zero follows the input for the last test case.

Output

For each test case output on a single line the area of the largest rectangle in the specified histogram. Remember that this rectangle must be aligned at the common base line.

Sample Input

7 2 1 4 5 1 3 3 
4 1000 1000 1000 1000 
0

Sample Output

8 4000

解题思路:

参考以上。

解题代码:G++

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;
const int N = 100000 + 10, INF = 0x3f3f3f3f;

struct node
{
    int index;
    int value;
    int parent;
    int child[2];

    friend bool operator< (node a, node b)
    {
        return a.index < b.index;
    }

    void init(int _index, int _value, int _parent)
    {
        index = _index;
        value = _value;
        parent = _parent;

        child[0] = child[1] = 0;
    }

} tree[N];

int root;
int top, stk[N];
ll ans;

//创建笛卡尔树
int cartesian_build(int n)
{
    for (int i = 1; i <= n; i++)
    {
        int k = i - 1;

        //一直找到比i位置小的位置k
        while (tree[k].value > tree[i].value) 
            k = tree[k].parent;

        //printf("i(%d - %d) k(%d - %d)\n", i, tree[i].value, k, tree[k].value);

        //将父节点的右子树放到自己的左子树上
        tree[i].child[0] = tree[k].child[1];
        //父节点的右子树重新指向
        tree[k].child[1] = i;
        //设置i的父节点
        tree[i].parent = k;
        //很多人没加这句,父节点关系就会乱掉
        tree[tree[i].child[0]].parent = i;
    }

    return tree[0].child[1];
}

int dfs(int x)
{
    if (!x)
        return 0;
    //计算最大值
    int sz = dfs(tree[x].child[0]);
    sz += dfs(tree[x].child[1]);
    ans = max(ans, (ll)(sz + 1) * tree[x].value);
    return sz + 1;
}

int main()
{
    int n, height;
    //freopen("test.txt", "r", stdin);

    while (scanf("%d", &n), n)
    {
        tree[0].init(0, 0, 0);

        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &height);
            //初始化每个节点
            tree[i].init(i, height, 0);
        }

        //创建笛卡尔树
        root = cartesian_build(n);
        //
        ans = 0;
        dfs(root);
        printf("%lld\n", ans);
    }

    return 0;
}

原文发布于微信公众号 - ACM算法日常(acm-clan)

原文发表时间:2018-09-06

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏LeetCode

LeetCode 114. Flatten Binary Tree to Linked List

关于二叉树的题目,最直接最简单的方法就是采用递归,因为二叉树具有天然的递归结构,实际上二叉树的定义就是用递归的思想来定义的:一个节点的左右子树任然是一个二叉树。

4400
来自专栏WD学习记录

Python数据结构与算法笔记(4)

前序遍历中,我们首先访问根节点,然后递归地做左侧子树的前序遍历,随后是右侧子树的递归前序。

13120
来自专栏机器学习与自然语言处理

二叉树的遍历:先序中序后序遍历的递归与非递归实现及层序遍历

  对于一种数据结构而言,遍历是常见操作。二叉树是一种基本的数据结构,是一种每个节点的儿子数目都不多于2的树。二叉树的节点声明如下: 1 typedef str...

35860
来自专栏来自地球男人的部落格

[LeetCode] 129. Sum Root to Leaf Numbers

【原题】 Given a binary tree containing digits from 0-9 only, each root-to-leaf pa...

224100
来自专栏架构之路

Combination Sum 组合数求和-Leetcode

原题: Given a set of candidate numbers (C) and a target number (T), find all uniqu...

33540
来自专栏我的技术专栏

数据结构图文解析之:二叉堆详解及C++模板实现

19650
来自专栏技术专栏

无向图最短路径问题

题目:无向图G有N个结点(1<N<=1000)及一些边,每一条边上带有正的权重值。 找到结点1到结点N的最短路径,或者输出不存在这样的路径。

57120
来自专栏mathor

线性表(一)

12320
来自专栏算法修养

LeetCode 102. Binary Tree Level Order Traversal

15840
来自专栏移动端开发

用OC和Swift一起说说二叉树

   一:在计算机科学中,二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)...

10850

扫码关注云+社区

领取腾讯云代金券